本文主要是介绍290. Word Pattern一个击败了100C++用户的代码,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目描述
Given a pattern and a string s, find if s 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 s.
Example 1:
Input: pattern = “abba”, s = “dog cat cat dog”
Output: true
Example 2:
Input: pattern = “abba”, s = “dog cat cat fish”
Output: false
Example 3:
Input: pattern = “aaaa”, s = “dog cat cat dog”
Output: false
Example 4:
Input: pattern = “jquery”, s = “jquery”
Output: false
Constrains:
- 1 <= pattern.length <= 300
- pattern contains only lower-case English letter.
- 1 <= s.length <= 3000
- s contains only lowercase English letters ans spaces ’ '.
- s does not contain any leading or trailing spaces.
解答思路
这题需要s包含的单词与pattern逐字母的进行映射,比如pattern是abba,那么s包含的字符也需要是对称的。这里需要注意当pattern与s一样的时候,输出为false,因为s应该与pattern每一个字母做映射,而不是整体。
思路类似205. Isomorphic String,做双向的映射。pattern每个字母与s里的每个单词做映射,单向的还不够,因为有可能出现abc,与"dog cat dog"对应时,a和c都对应上dog了。
class Solution {
public:bool wordPattern(string pattern, const string& s) { return wordPatternHelp(pattern, s) && wordPatternHelp2(pattern, s);}void split_string(vector<string> &ves, string str){istringstream ss(str);string s;while(ss >> s){ves.push_back(s);}}bool wordPatternHelp(string pattern, string s) {unordered_map<char, string> m;vector<string> ves;split_string(ves, s);if(pattern.length() > ves.size())return false;for(int i = 0; i < pattern.length(); i++){if(m.find(pattern[i]) != m.end()){if(m[pattern[i]] != ves[i])return false;}elsem[pattern[i]] = ves[i];}return true;}bool wordPatternHelp2(string pattern, string s){unordered_map<string, char> m;vector<string> ves;split_string(ves, s);for(int i = 0; i < ves.size(); i++){if(m.find(ves[i]) != m.end()){if(m[ves[i]] != pattern[i])return false;}elsem[ves[i]] = pattern[i];}return true;}
};
这篇关于290. Word Pattern一个击败了100C++用户的代码的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!