290. Word Pattern(词语匹配)
1 问题描述
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
.
已知字符串pattern与字符串str,确认str是否与pattern匹配。str与pattern匹配代表字符 串str中的单词pattern中的字符一一对应。(其中pattern中只包含小写字符,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
2 C++实现
class Solution {
public:
bool wordPattern(string pattern, string str) {
map<string, char> word_map;
char used[128] = {0};
int pos = 0;
string word; //存储未知变量
str.push_back(' '); //为了读取最后一个单词
for(int i=0; i<str.length(); i++) {
if(str[i] == ' ') {
if(pos == pattern.length())
return false;
if(word_map.find(word) == word_map.end()) {
if(used[pattern[pos]])
return false;
word_map[word] = pattern[pos];
used[pattern[pos]] = 1;
}
else {
if(word_map[word] != pattern[pos])
return false;
}
pos++;
word = "";
}
else {
word += str[i];
}
}
if (pos != pattern.length()){
return false;
}
return true;
}
};
继续阅读
- 我的微信小程序
- 这是我的微信小程序扫一扫
-
- 我的微信公众号
- 我的微信公众号扫一扫
-
评论