题目：给一个单 词和一个pattern。返回True or False判定单词和pattern是否match。A full match is a bijection between a letter in pattern and a non-empty substring in str.

Examples:

pattern = “abab”, str = “redblueredblue” should return true.

pattern = “aaaa”, str = “asdasdasdasd” should return true.

pattern = “aabb”, str = “xyzabcxzyabc” should return false.

思路：

reference: https://leetcode.com/problems/word-pattern-ii/discuss/73664
Keep 一个 char to string map,  key(char)代表单个字符的pattern，value(string)为单个字符对应的string。保证每个char对应一个string
再keep一个set记录已经使用过的char对应的string。保证每个string对应一个char。

backtrack  match 过程举例：
pattern = “abab”, str = “redblueredblue”
先let “a” match “r”, “b” match “e”，此时pattern中第二个“a” 不 match “d”, backtrack,
“b” match “ed”，此时pattern中第二个“a” 不 match “b”, backtrack,
…
“b” match “ed..e”, 此时string结束，backtrack.
let “a” match “re”, “b” match “d”, 此时pattern中第二个”a” 不match “b”, backtrack,
                                …
let “a” match “red”, “b” match “ blue”,  此时pattern中第二个”a” match “red”,   第二个b match “blue” pattern 和 string都到末尾。返回true。

由例子可得，我们只要写一个recursion返回是否能match , 从 i index字符开始的string 和 从j index字符pattern即可。并且使用 Mapmap 和 Setset 来keep bijection mapping。

Big-O Analysis,
Pattern length:m. String length:n;
Running time: O (n^m)
Space: O (m+ n)  m 为map大小（char对应的value的个数），第二个n为set worst case element个数。

public class Solution {

  public boolean wordPatternMatch(String pattern, String str) {
    Map<Character, String> map = new HashMap<>();
    Set<String> set = new HashSet<>();

    return isMatch(str, 0, pattern, 0, map, set);
  }

  boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map, Set<String> set) {
    // base case
    if (i == str.length() && j == pat.length()) return true;
    if (i == str.length() || j == pat.length()) return false;

    // get current pattern character
    char c = pat.charAt(j);

    // if the pattern character exists
    if (map.containsKey(c)) {
      String s = map.get(c);

      // then check if we can use it to match str[i...i+s.length()]
      if (!str.startsWith(s, i)) {
        return false;
      }

      // if it can match, great, continue to match the rest
      return isMatch(str, i + s.length(), pat, j + 1, map, set);
    }

    // pattern character does not exist in the map
    for (int k = i; k < str.length(); k++) {
      String p = str.substring(i, k + 1);

      if (set.contains(p)) {
        continue;
      }

      // create or update it
      map.put(c, p);
      set.add(p);

      // continue to match the rest
      if (isMatch(str, k + 1, pat, j + 1, map, set)) {
        return true;
      }

      // backtracking
      map.remove(c);
      set.remove(p);
    }

    // we've tried our best but still no luck
    return false;
  }

}

算法排名比较低，应该还有很大的空间可以improve。

使用map.values()代替多余的hashset记录bijection关系可以improve时间(节省了对set的操作时间）和空间（少了一个hashset).

Running time: O (n^m)
Space: O (n)

public class Solution {

  public boolean wordPatternMatch(String pattern, String str) {
    Map<Character, String> map = new HashMap<>();

    return isMatch(str, 0, pattern, 0, map);
  }

  boolean isMatch(String str, int i, String pat, int j, Map<Character, String> map) {
    // base case
    if (i == str.length() && j == pat.length()) return true;
    if (i == str.length() || j == pat.length()) return false;

    // get current pattern character
    char c = pat.charAt(j);

    // if the pattern character exists
    if (map.containsKey(c)) {
      String s = map.get(c);

      // then check if we can use it to match str[i...i+s.length()]
      if (!str.startsWith(s, i)) {
        return false;
      }

      // if it can match, great, continue to match the rest
      return isMatch(str, i + s.length(), pat, j + 1, map);
    }

    // pattern character does not exist in the map
    for (int k = i; k < str.length(); k++) {
      String p = str.substring(i, k + 1);

      if (map.values().contains(p)) {
        continue;
      }

      // create or update it
      map.put(c, p);

      // continue to match the rest
      if (isMatch(str, k + 1, pat, j + 1, map)) {
        return true;
      }

      // backtracking
      map.remove(c);
    }

    // we've tried our best but still no luck
    return false;
  }

}

improve了23ms.

欢迎大神们继续improve算法。

长按扫码关注公众号