My C++ code (0 ms, using unordered_map to save 1-2-1 mapping)


  • 0
    D

    The basic idea is

    1. using a istringstream to break str into array of words

    2. Use a vector to save pattern char->word mapping and an unordered_map to save word->pattern char mapping

    3. For each for loop iteration, get a new word to curS,
      a) first check if pattern reaches its end, if so, return false;
      b) if the mapping pattern[i]->curS doesn't hold,
      a) check if pattern[i] and curS both are NOT mapped before, if so, save pattern[i]<->curS 1-2-1 mapping
      b) otherwise, return false;

    4. after going through all the words, check if pattern reaches its end, if so, return true, otherwise, false

      class Solution {
      public:
      bool wordPattern(string pattern, string str) {
      vector<string> map(26, "");
      unordered_map<string, int> rev_map;
      istringstream in(str);
      string curS;
      int i;
      for(i=0; (in>>curS) ; ++i)
      {
      if(!(pattern[i])) return false; // step(3a)
      if(map[pattern[i]-'a'] != curS ) // step(3b)
      {
      if(map[pattern[i]-'a']!="" || rev_map.count(curS)) return false; // step(3bb)
      map[pattern[i]-'a'] = curS; //step(3ba)
      rev_map[curS] = pattern[i]-'a';
      }
      }
      return !(pattern[i]); // step(4)
      }
      };


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.