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

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false

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;
}

Complexity

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

---