[LeetCode] Problem 290 - Word Pattern

Posted on | In ,

Given a pattern and a string str, find if str 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 str.

Example

No.1

Input: pattern = “abba”, str = “dog cat cat dog”

Output: true

No.2

Input:pattern = “abba”, str = “dog cat cat fish”

Output: false

No.3

Input: pattern = “aaaa”, str = “dog cat cat dog”

Output: false

No.4

Input: pattern = “abba”, str = “dog dog dog dog”

Output: false

Notes

You may assume pattern contains only lowercase letters, and str contains lowercase letters that may be separated by a single space.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean wordPattern(String pattern, String str) {
    Map<String, Character> map = new HashMap<>();
    Set<Character> set = new HashSet<>();
    String[] words = str.split(" ");
    
    if (words.length != pattern.length())
        return false;

    for (int i = 0; i < words.length; i++) {
        char p = pattern.charAt(i);

        if (!map.containsKey(words[i])) {
            if (set.contains(p))
                return false;

            map.put(words[i], p);
            set.add(p);
        }
        else if (map.get(words[i]) != p)
            return false;
    }

    return true;
}