[LintCode] Problem 829 - Word Pattern II

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 substring in str.(i.e if a corresponds to s, then b cannot correspond to s. For example, given pattern = “ab”, str = “ss”, return false.)

Note

You may assume both pattern and str contains only lowercase letters.

Example

No.1

Input:
pattern = “abab”
str = “redblueredblue”

Output: true

Explanation: “a”->”red”,”b”->”blue”

No.2

Input:
pattern = “aaaa”
str = “asdasdasdasd”

Output: true

Explanation: “a”->”asd”

No.3

Input:
pattern = “aabb”
str = “xyzabcxzyabc”

Output: false

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
25
26
27
28
29
30
31
32
33
34
35
public boolean wordPatternMatch(String pattern, String str) {
    Map<String, Character> map = new HashMap<>();
    Set<Character> set = new HashSet<>();
    return dfs(map, set, pattern, 0, str, 0);
}

private boolean dfs(Map<String, Character> map, Set<Character> set, String pattern, int p, String str, int s) {
    if (p == pattern.length() && s == str.length())
        return true;
    else if (p == pattern.length() || s == str.length())
        return false;

    char ch = pattern.charAt(p);

    for (int i = s; i < str.length(); i++) {
        String word = str.substring(s, i + 1);

        if (!map.containsKey(word) && !set.contains(ch)) {
            map.put(word, ch);
            set.add(ch);

            if (dfs(map, set, pattern, p + 1, str, i + 1))
                return true;

            map.remove(word);
            set.remove(ch);
        }
        else if (map.containsKey(word) && map.get(word) == ch) {
            if (dfs(map, set, pattern, p + 1, str, i + 1))
                return true;
        }
    }

    return false;
}