LeetCode290. Word Pattern（模拟）

LeetCode290. Word Pattern（模拟）

• Easy
• Accepted：128,851
• Submissions：374,057

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:

You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

---

链接

https://leetcode.com/problems/word-pattern/

题意

给定一个模式pattern 和一个字符串str，判断这个字符串是否符合该模式，看下样例就明白了。

题解

拿unordered_map匹配一下就好了，将字符串和对应的模式字符建立映射关系，然后进行判断即可。注意一下要按空格对字符串str进行分割，用string的substr完成。

代码

• Runtime: 4 ms, faster than 100.00% of C++ online submissions for Word Pattern.
• Memory Usage: 8.7 MB, less than 100.00% of C++ online submissions for Word Pattern.

class Solution {
public:
    bool wordPattern(string pattern, string str) {
        vector <string> vt;
        stringSpilt(str, vt);
        int n = pattern.length(), m = vt.size();
        unordered_map<string, char> umap;
        bool vis[256]; // 对模式的字符进行标记
        memset(vis, 0, sizeof vis);
        int i;
        for (i = 0; i < m; ++i)
        {

            if (!umap.count(vt[i]) && !vis[pattern[i]]) // 字符串不在map中且模式字符没用过就加入
            {
                umap.insert(make_pair(vt[i], pattern[i]));
                vis[pattern[i]] = true;
            }
            if (umap.count(vt[i]) > 0 && umap[vt[i]] != pattern[i]) // 在map中则模式字符要相同
                break;
            if (!umap.count(vt[i]) && vis[pattern[i]]) // 不在map中则模式字符要没用过
                break;
        }
        return  i == m && i == n;
    }

    void stringSpilt(string s, vector<string> &vt) // 对字符串进行分割
    {
        int n = s.length();
        vector <int> pos;
        pos.push_back(0);
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == ' ')
                pos.push_back(i + 1);
        }
        pos.push_back(n + 1);
        int cnt = pos.size();
        for (int i = 0; i < cnt - 1; ++i)
        {
            // cout << s.substr(pos[i], pos[i+1] - pos[i] - 1);
            // cout << " " << pos[i] << " " << pos[i+1] - pos[i] - 1 << endl;
            vt.push_back(s.substr(pos[i], pos[i+1] - pos[i] - 1));
        }
    }
};

注意vis数组要初始化，不然会RE。

补充

还有更好的对字符串进行分割的方法，使用istringstream（istringstream是C++里面的一种输入输出控制类，它可以创建一个对象，然后这个对象就可以绑定一行字符串，然后以空格为分隔符把该行分隔开来）。然后把就有了一个更优美的解法。

bool wordPattern(string pattern, string str) {
        istringstream strcin(str);
        string s;
        vector<string> vs;
        while(strcin >> s) vs.push_back(s);
        if (pattern.size() != vs.size()) return false;
        map<string, char> s2c;
        map<char, string> c2s;
        for (int i = 0; i < vs.size(); ++i) {
            if (s2c[vs[i]] == 0 && c2s[pattern[i]] == "") { 
                s2c[vs[i]] = pattern[i]; 
                c2s[pattern[i]] = vs[i]; 
                continue; 
            }
            if (s2c[vs[i]] != pattern[i]) return false;
        }
        return true;
    }

---

The end.
2019年2月15日 星期五