本文主要是介绍leetcode 290: Word Pattern,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
问题描述:
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.
Examples:
pattern = “abba”, str = “dog cat cat dog” should return true.
pattern = “abba”, str = “dog cat cat fish” should return false.
pattern = “aaaa”, str = “dog cat cat dog” should return false.
pattern = “abba”, str = “dog dog dog dog” should return false.
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
思路:
首先把str给分割成单词数组,然后用笨方法,保存双向映射,这就是为什么代码中设置两个map。遍历数组,用map来查找和插入映射。
代码:
class Solution {
public:bool wordPattern(string pattern, string str) {//split into word listvector<string> wordlist;string::size_type pos;str += " ";int size = str.size();for (int i = 0; i < size; i++){pos = str.find(" ", i); //find the space positionif (pos < size){string word = str.substr(i, pos - i); //extract the wordif (word != "") //record the word{wordlist.push_back(word);}i = pos;}}int w_size = wordlist.size();int p_size = pattern.size();if (w_size != p_size) return false;map<char, string> c2s_mapped; //map char to stringmap<string, char> s2c_mapped; //map string to charfor (int i = 0; i < p_size; i++){char c_now = pattern[i];string s_now = wordlist[i];map<char, string>::iterator it_c2s = c2s_mapped.find(c_now);if (it_c2s != c2s_mapped.end()) //found{if (it_c2s->second != s_now) return false;}else //not found{map<string, char>::iterator it_s2c = s2c_mapped.find(s_now);if (it_s2c != s2c_mapped.end()) return false;c2s_mapped.insert(pair<char, string>(c_now, s_now));s2c_mapped.insert(pair<string, char>(s_now, c_now));}}return true;}
};
这篇关于leetcode 290: Word Pattern的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!