leetcode 290： Word Pattern

2023-10-14 02:58

文章标签 leetcode word pattern 290

本文主要是介绍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;}
};