DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

290. Word Pattern

Description

Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Enter fullscreen mode Exit fullscreen mode

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Enter fullscreen mode Exit fullscreen mode

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Enter fullscreen mode Exit fullscreen mode

Constraints:

  • 1 <= pattern.length <= 300
  • pattern contains only lower-case English letters.
  • 1 <= s.length <= 3000
  • s contains only lowercase English letters and spaces ' '.
  • s does not contain any leading or trailing spaces.
  • All the words in s are separated by a single space.

Solutions

Solution 1

Intuition

  1. compare lengths
  2. build relations(map): c → w
    1. map(c) ≠ w
    2. w was already existed

Code

public boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (words.length != pattern.length()) {
        return false;
    }
    HashMap<Character, String> map = new HashMap<>();

    for (int i = 0; i < words.length; i++) {
        char c = pattern.charAt(i);
        String w = words[i];
        if (map.containsKey(c)) {
            if (!map.get(c).equals(w)) {
                return false;
            }
        } else {
            if (map.containsValue(w)) {
                return false;
            }
            map.put(c, w);
        }
    }

    return true;
}
Enter fullscreen mode Exit fullscreen mode

Complexity

  • Time: O(n)
  • Space: O(n)

Discussion (0)