leetcode 290. Word Pattern 、lintcode 829. Word Pattern II
290. Word Pattern
istringstream 是将字符串变成字符串迭代器一样，将字符串流在依次拿出，比较好的是，它不会将空格作为流，这样就实现了字符串的空格切割。
C++引入了ostringstream、istringstream、stringstream这三个类，要使用他们创建对象就必须包含sstream.h头文件。
istringstream类用于执行C++风格的串流的输入操作。
ostringstream类用于执行C风格的串流的输出操作。
strstream类同时可以支持C风格的串流的输入输出操作。
1.本题中str是带空格的字符串，需要将每个词根据提取出来，就使用istringstream。
2.本题要求的是pattern中的字符和str中的单词是一一对应的，所以不仅要判断当前pattern字符与存储在hash中的的映射是否相同，还需要判断hash中映射的string是否与当前string相同。
3.可能存在pattern和str个数不一样的情况，所以最后使用i == n来判断。
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char,string> m;
istringstream in(str);
int i = ,n = pattern.size();
for(string tmp;in >> tmp;i++){
if(m.find(pattern[i]) == m.end()){
for(auto it = m.begin();it != m.end();it++){
if(it->second == tmp)
return false;
}
m[pattern[i]] = tmp;
}
else{
if(m[pattern[i]] != tmp)
return false;
}
}
return i == n;
}
};
这种情况就是两者个数不相同。
Input:
"jquery"
"jquery"
Output:
true
Expected:
false
829. Word Pattern II
https://www.cnblogs.com/grandyang/p/5325761.html
不知道哪个单词对应哪个词，就用递归去搜索每种可能性
class Solution {
public:
/**
* @param pattern: a string,denote pattern string
* @param str: a string, denote matching string
* @return: a boolean
*/
bool wordPatternMatch(string &pattern, string &str) {
// write your code here
unordered_map<char,string> m;
int index1 = ,index2 = ;
return wordPatternMatch(pattern,index1,str,index2,m);
}
bool wordPatternMatch(string &pattern,int index1,string &str,int index2,unordered_map<char,string> &m){
if(index1 == pattern.size() && index2 == str.size())
return true;
if(index1 == pattern.size() || index2 == str.size())
return false;
char word = pattern[index1];
for(int i = index2;i < str.size();i++){
string tmp = str.substr(index2,i - index2 + );
if(m.count(word) && m[word] == tmp){
if(wordPatternMatch(pattern,index1+,str,i+,m))
return true;
}
else if(!m.count(word)){
bool flag = false;
for(auto it : m){
if(it.second == tmp)
flag = true;
}
if(!flag){
m[word] = tmp;
if(wordPatternMatch(pattern,index1+,str,i+,m))
return true;
m.erase(word);
}
}
}
}
};
自己又写了一个版本：
其实主要是如果当前不满足true的条件，就继续遍历
if(m.find(word) != m.end()){
if(m[word] == tmp){
if(wordPatternMatch(pattern,str,index1+1,i+1,m))
return true;
}
}
如果word != tmp，不做任何处理直接继续遍历下一个位置就好了
if(flag)
continue;
如果在map中找到了tmp，也就不满足条件，这个时候也不做任何处理，直接继续遍历就好了
class Solution {
public:
/**
* @param pattern: a string,denote pattern string
* @param str: a string, denote matching string
* @return: a boolean
*/
bool wordPatternMatch(string &pattern, string &str) {
// write your code here
unordered_map<char,string> m;
int index1 = ,index2 = ;
return wordPatternMatch(pattern,str,index1,index2,m);
}
bool wordPatternMatch(string pattern,string str,int index1,int index2,unordered_map<char,string> m){
if(index1 == pattern.size() && index2 == str.size())
return true;
else if(index1 == pattern.size() || index2 == str.size())
return false;
char word = pattern[index1];
for(int i = index2;i < str.size();i++){
string tmp = str.substr(index2,i - index2 + );
if(m.find(word) != m.end()){
if(m[word] == tmp){
if(wordPatternMatch(pattern,str,index1+,i+,m))
return true;
}
}
else{
bool flag = false;
for(auto it = m.begin();it != m.end();it++){
if(it->second == tmp){
flag = true;
break;
}
}
if(flag)
continue;
m[word] = tmp;
if(wordPatternMatch(pattern,str,index1+,i+,m))
return true;
m.erase(word);
}
}
}
};
最新文章
- LINQ系列：LINQ to SQL Group by/Having分组
- java基础类型、包装器
- NOIP2013 花匠
- express新旧语法对比
- （六）6.10 Neurons Networks implements of softmax regression
- java 定义mysql树形菜单
- 负载均衡 > 常见问题
- java设计模式之单例模式(七种方法)
- 基于Ceph快照的异地灾备设计
- 分布式开放消息系统(RocketMQ)的原理与实践（转）
- c/c++面试准备笔记1
- Unity 3D 之贪吃蛇 Text 心得 & Audio
- 如何将阿里云mysql RDS备份文件恢复到自建数据库
- java通过http服务执行shell命令
- 一本通1642【例 2】Fibonacci 第 n 项
- C#.NET常见问题(FAQ)-构造器constructor有什么用
- python 百度图片爬虫
- JavaStuNote 5
- 购物车中的input输入框只能输入数字和输入为0的时候默认为1
- [MySQL] AUTO_INCREMENT lock Handing in InnoDB