Word Pattern

• Easy
• tag: HashMap(API), String
• Similar: Bulls & Cows, Isomorphic Strings

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.
• Examples:
  • pattern = "abba", str = "dog cat cat dog" should return true.
  • pattern = "abba", str = "dog cat cat fish" should return false.
  • pattern = "aaaa", str = "dog cat cat dog" should return false.
  • pattern = "abba", str = "dog dog dog dog" should return false.
• Notes:
  • You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

思路

• 想法很简单, 就是建立HashMap, 然后看对不对应.

idea 1: 我的简单使用Map的写法

• one-pass. 如果不存在, 就建立map. 若存在, 就看对不对应.
• 代码如下:

public boolean wordPatternTTT(String pattern, String str) {
    Map<Character, String> map = new HashMap<>();
    String[] Arr = str.split("\\s+");
    if(Arr.length!= pattern.length())
      return false;
    for (int i = 0; i < pattern.length(); ++i) {
      char a = pattern.charAt(i);
      if (map.containsKey(a)) {
        if (!map.get(a).equals(Arr[i])) {
          return false;
        }
      }
      else {
        if (map.containsValue(Arr[i])) {  // 容易错, 类似isomorphic string
          return false;
        }
        map.put(a, Arr[i]);
      }
    }
    return true;
  }

• 代码里面有个容易错的地方, 和isomorphic String一样. 就是: a->dog的话. b就不能map到dog. 所以建立map之前, 要检查一下dog有没有被match过. 否则会出现: "ab"->"dog dog", 然后我返回了: true的情况. 就是因为没有检查x/y中y有没有被映射过.

idea 2: 其实可以使用Map API来做.

• 对于各种语言, 除了语法, 就是API, collection要熟练. 就像Android/RTOS的API要熟练.
• 我之前只知道stack/queue/map/set的put/get. 但其实put/set是有return value的: 若之前已经map了, 则replace旧映射的同时, return 旧映射. 若还没有映射, 返回null.
• 通过以上API的return, 想到Isomorphic Strings的256+256 table比较法.
• 代码如下:

public boolean wordPatternTTT(String pattern, String str) {
    Map<Character, String> map = new HashMap<>();
    String[] Arr = str.split("\\s+");
    if(Arr.length!= pattern.length())
      return false;
    for (int i = 0; i < pattern.length(); ++i) {
      char a = pattern.charAt(i);
      if (map.put(a, i) != map.put(Arr[i],i)) {   // 很像Isomorphic String吧?
        return false;
      }
    }
    return true;
  }