https://leetcode.com/problems/word-pattern/description/
题目
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.
题目翻译
题目解析
参考答案
#include <iostream>
#include <string>
#include <string.h>
#include <vector>
#include <map>
using namespace std;
class Solution {
public:
bool wordPattern(string pattern, string str)
{
map<char, string> mapPatternToString;
map<string, char> mapStringToPattern;
vector<string> vecSubString = splitString(str, ' ');
if (vecSubString.size() != pattern.size())
{
return false;
}
for (int i = 0; i < vecSubString.size(); i++)
{
char c = pattern[i];
map<char, string>::iterator iterPTS = mapPatternToString.find(c);
if (iterPTS == mapPatternToString.end())
{
mapPatternToString.insert(std::pair<char, string>(c, vecSubString[i]));
}
else
{
if (strcmp(iterPTS->second.c_str(), vecSubString[i].c_str()) != 0)
{
return false;
}
}
map<string, char>::iterator iterSTP = mapStringToPattern.find(vecSubString[i]);
if (iterSTP == mapStringToPattern.end())
{
mapStringToPattern.insert(std::pair<string, char>(vecSubString[i], c));
}
else
{
if (iterSTP->second != c)
{
return false;
}
}
}
return true;
}
vector<string> splitString(string str, char sep)
{
vector<string> result;
string strSubString;
const char * pcStr = str.data();
for (int i = 0; i <= str.size(); i++)
{
if (i == str.size() || str[i] == ' ')
{
strSubString.append(1, '\0');
result.push_back(strSubString);
strSubString.clear();
}
else
{
strSubString.append(1, str[i]);
}
}
return result;
}
};
int main()
{
Solution o;
bool bRet = o.wordPattern("jquery", "jquery");
return 0;
}
