0ms C++, use string::find


  • 0
    R

    Create two maps to maintain the last traverse index for the current character or substring. Then traverse the pattern and str at the same time, use string::find to split str, and update the pos.

    class Solution {
    public:
        bool wordPattern(string pattern, string str) {
            str += ' '; // add a dummy space to find the last substring
            unordered_map<char, int> pmap;
            unordered_map<string, int> smap;
            size_t pos = 0;
            for (int i = 0; i < pattern.size(); i++) {
                size_t nextPos = str.find(' ', pos);
                if (nextPos == string::npos) return false;
                
                string substr(str.substr(pos, nextPos - pos));
                if (pmap[pattern[i]] != smap[substr]) return false;
                
                pmap[pattern[i]] = i + 1;
                smap[substr] = i + 1;
                pos = nextPos + 1;
            }
            return pos == str.size();
        }
    };
    

Log in to reply
 

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