[LeetCode]290. Word Pattern

发表于 | 更新于: | 分类于 | | 阅读次数:

Problem

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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 that may be separated by a single space.

Solution

Analysis

模式匹配问题.

给定两个字符串:pattern,str. 其中str是用单个空格切分的字符串,判断两个字符串模式是否匹配. 匹配: 双射. a->b, b->a.

有一个需要注意的是,两者的对应关系并不是对等的,不是char -> char, 而是 char-> string. 而string则是str中用空格切分出来的子串,所以需要找到这样的由空格切分的子串数组,匹配问题就是一个hash表映射的问题,确保a2b,以及b2a都是正确的.

  • 如果当前字符出现在hash表中,判断当前对应关系和hash表中的记录结果是否一致,如果一致,则继续判断;如果不一致,返回false;
  • 如果当前字符没有出现在hash表中,则记录这对对应关系;

匹配(双射),本质上还是一个函数.

具体实现,我们可以将结果都映射到同一个参考系上(做一次抽象,比如都是AABB型),然后做对比. 也可以相互映射,同时判断各自的映射结果(这里的实现方法就是相互映射,同时判断).

此外还要注意corner case, 两个字符串存在空串情况,返回false.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool wordPattern(string pattern, string str) {

        if (pattern.empty() || str.empty()) return false;
        
        unordered_map<char, string> a2b;
        unordered_map<string, char> b2a;
        vector<string> strs;// 字符串切分结果.
        
        for (int i=0; i< str.size(); ){// 相等于字符串的split函数
            int j = i;
            
            while (str[j] != ' ' && j < str.size())
                j++;
            strs.push_back(str.substr(i, j-i));
            i = j + 1;
        }
        // 判断两个串长度是否相等,及时剪枝
        if (strs.size() != pattern.size())
             return false;
        for (int i=0; i< pattern.size(); i++){
            if (a2b.find(pattern[i]) == a2b.end()){
                a2b[pattern[i]] = strs[i];
            }
            else if (a2b[pattern[i]] != strs[i])
                return false;
            
            if (b2a.find(strs[i]) == b2a.end())
                b2a[strs[i]] = pattern[i];
            else if (b2a[strs[i]] != pattern[i])
                return false;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool wordPattern(string pattern, string str) {
        unordered_map<char, int> m1;
        unordered_map<string, int> m2;
        istringstream ss(str);// istringstream
        
        int i = 0, size = pattern.size();
        
        for (string word; ss >> word; i++){//istringstream可以通过输出流>>得到由空格切分的单个内容,然后通过循环得到所有的内容
            if (i == size || m1[pattern[i]] != m2[word])
                return false;
            m1[pattern[i]] = m2[word] = i + 1;
        }
        
        return i == size;
    }
};

References

https://www.cnblogs.com/grandyang/p/4857022.html

您的支持就是我更新的最大动力!谢谢!