Word Pattern

题目来源
一道判断模式是否匹配的题目,感觉不难,但是需要考虑各种情况,然后导致submit了多次才AC。感觉应该有简单方法。
代码如下:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        int n1 = pattern.size(), n2 = str.size();
        unordered_map<char, string> maps;
        int l = 0, r = 0;
        for (int i=0; i<n1; i++) {
            while (str[r+1] != ' ' && r < n2 - 1) {
                r++;
            }
            if (r >= n2)
                return false;
            string word = str.substr(l, r-l+1);
            if (maps.count(pattern[i]) == 0)
                maps[pattern[i]] = word;
            else if (maps[pattern[i]] != word)
                return false;
            l = r + 2;
            r = l;
        }
        if (r < n2)
            return false;
        unordered_map<char, string>::iterator iter;
        unordered_set<string> maps2;
        for (iter = maps.begin(); iter != maps.end(); iter++)
            if (maps2.count(iter->second) == 0)
                maps2.insert(iter->second);
            else
                return false;
        return true;
    }
};

果然,两个简化办法,一个把str当做输入,直接去掉了分割操作,另一个是存储的是位置,去掉了判断比如abba对应"dog dog dog dog"这样的例子,不能不服!
代码如下:

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        int n = pattern.size();
        unordered_map<char, int> maps1;
        unordered_map<string, int> maps2;
        istringstream in(str);
        int i = 0;
        for (string word; in >> word; i++) {
            if (i == n || maps1[pattern[i]] != maps2[word])
                return false;
            maps1[pattern[i]] = maps2[word] = i + 1;
        }
        return i == n;
    }
};
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容