Leetcode

Word Pattern

  • Time:O(n)
  • Space:O(n)

C++

class Solution {
 public:
  bool wordPattern(string pattern, string str) {
    const int n = pattern.length();
    istringstream iss(str);
    vector<int> charToIndex(128);
    unordered_map<string, int> stringToIndex;

    int i = 0;
    for (string word; iss >> word; ++i) {
      if (i == n)  // out of bound
        return false;
      if (charToIndex[pattern[i]] != stringToIndex[word])
        return false;
      charToIndex[pattern[i]] = i + 1;
      stringToIndex[word] = i + 1;
    }

    return i == n;
  }
};

JAVA

class Solution {
  public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
      return false;

    Map<Character, Integer> charToIndex = new HashMap<>();
    Map<String, Integer> stringToIndex = new HashMap<>();

    for (Integer i = 0; i < pattern.length(); ++i)
      if (charToIndex.put(pattern.charAt(i), i) != stringToIndex.put(words[i], i))
        return false;

    return true;
  }
}

Python

class Solution:
  def wordPattern(self, pattern: str, str: str) -> bool:
    t = str.split()
    return [*map(pattern.index, pattern)] == [*map(t.index, t)]