Tuesday, September 12, 2017

290. Word Pattern

https://leetcode.com/problems/word-pattern/description/
Solution 1.0 Read the string one by one and compare. Use stringstream the read. (0 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        string item;
        int i=0, n=pattern.size();
        for(; getline(ss, item, ' ');i++) {
            if(i==n || mp[pattern[i]] != ms[item]) return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;

    }
Solution 1.2 Use istringstream
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        istringstream in(str);
        int i = 0, n = pattern.size();
        for(string item; in>>item;i++) {
            if(i==n || mp[pattern[i]]!=ms[item])
                return false;
            mp[pattern[i]] = i+1;
            ms[item] = i+1;
        }
        return i==n;
    }
Solution 1.1 Convert the string to a vector<string> and compare. (3 ms)
    bool wordPattern(string pattern, string str) {
        unordered_map<char,int> mp;
        unordered_map<string,int> ms;
        stringstream ss(str);
        vector<string> s;
        string item;
        while(getline(ss, item, ' ')) {
            s.push_back(item);
        }
        if(pattern.size() != s.size()) return false;
        for(int i=0; i<s.size();i++) {
            if(!mp.count(pattern[i]) && !ms.count(s[i])) {
                mp[pattern[i]] = i+1;
                ms[s[i]] = i+1;
            }
            if(!mp.count(pattern[i]) || !ms.count(s[i])) return false;
            if(mp[pattern[i]] != ms[s[i]]) return false;
        }
        return true;
    }

No comments:

Post a Comment