Word Pattern II

Given apatternand a stringstr, find ifstrfollows the same pattern.

Here follow means a full match, such that there is a bijection between a letter inpatternand a non-empty substring instr.(i.e ifacorresponds tos, thenbcannot correspond tos. For example, given pattern ="ab", str ="ss", returnfalse.)

Notice：

You may assume bothpatternandstrcontains only lowercase letters.

Example

Given pattern ="abab", str ="redblueredblue", returntrue. Given pattern ="aaaa", str ="asdasdasdasd", returntrue. Given pattern ="aabb", str ="xyzabcxzyabc", returnfalse.

Note

类似Word Pattern，不过这里没有给你分词了，需要自己暴力去试，依旧需要双向mapping（Map + Set）

逻辑：

• 如果map包含字符，看看当前substring是不是以这个map的value开头，不是就false了，递归传递子串

  p.substring(1), 
  s.substring(map.get(c).length())

• 如果map不包含字符，暴力一个个位置拆分去试，for循环，如果set里面有，则continue继续找（必须双向映射）

  p.substring(1)
  s.substring(i + 1)

Time：O(2^len_str) (因为隐含条件是 len_pattern <= len_str)

Space： O(2^len_str * wordLength)

Code

public class Solution {
    /**
     * @param pattern: a string,denote pattern string
     * @param str: a string, denote matching string
     * @return: a boolean
     */
    public boolean wordPatternMatch(String p, String s) {
        // write your code here
        Map<Character, String> map = new HashMap<>();
        Set<String> set = new HashSet<>();

        return helper(p, s, map, set);
    }

    private boolean helper(String p, String s, 
                           Map<Character, String> map,
                           Set<String> set) {
        if (p.length() == 0) {
            return s.length() == 0;
        }                       

        char c = p.charAt(0);
        if (map.containsKey(c)) {
            if (!s.startsWith(map.get(c))) {
                return false;
            }

            return helper(p.substring(1), 
                          s.substring(map.get(c).length()),
                          map, set);
        } else {
            for (int i = 0; i < s.length(); i++) {
                String word = s.substring(0, i + 1);
                if (set.contains(word)) {
                    continue;
                }
                map.put(c, word);
                set.add(word);
                if (helper(p.substring(1), 
                           s.substring(i + 1), 
                           map, set)) {
                    return true;           
                }
                set.remove(word);
                map.remove(c);
            }
        }

        return false;
    }
}