## Tuesday, December 1, 2015

### LeetCode OJ - Word Pattern

Problem:

Please find the problem here.

Solution:

A simple problem, just to be careful with the cases.

• Too many patterns.
• Too many tokens in the string.
• One pattern match multiple tokens
• One token match multiple patterns

Once the cases are carefully enumerated, the coding of it is rather trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/word-pattern/

#include "LEET_WORD_PATTERN.h"
#include <map>
#include <string>
#include <iostream>

using namespace std;

namespace _LEET_WORD_PATTERN
{
class Solution
{
private:
bool match(map<char, string>& p_to_s, map<string, char>& s_to_p, char p, string s)
{
map<char, string>::iterator p_to_s_probe = p_to_s.find(p);
map<string, char>::iterator s_to_p_probe = s_to_p.find(s);
if (p_to_s_probe == p_to_s.end() && s_to_p_probe == s_to_p.end())
{
p_to_s.insert(pair<char, string>(p, s));
s_to_p.insert(pair<string, char>(s, p));
return true;
}
else if(p_to_s_probe != p_to_s.end() && s_to_p_probe != s_to_p.end())
{
return (p_to_s_probe->second == s) && (s_to_p_probe->second == p);
}
else
{
return false;
}
}
public:
bool wordPattern(string pattern, string str)
{
map<char, string> p_to_s;
map<string, char> s_to_p;
unsigned int s_i = 0;
unsigned int p_i = 0;
for (unsigned int s_e = 0; s_e < str.size(); s_e++)
{
if (str[s_e] == ' ')
{
if (p_i < pattern.size())
{
if (match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, s_e - s_i)))
{
s_i = s_e + 1;
}
else
{
return false;
}
}
else
{
return false;
}
}
}
if (p_i < pattern.size())
{
if (!match(p_to_s, s_to_p, pattern[p_i++], str.substr(s_i, str.size() - s_i)))
{
return false;
}
}
else
{
return false;
}
if (p_i != pattern.size())
{
return false;
}
return true;
}
};
};

using namespace _LEET_WORD_PATTERN;

int LEET_WORD_PATTERN()
{
Solution solution;
cout << solution.wordPattern("abba", "dog cat cat dog") << endl;
cout << !solution.wordPattern("abba", "dog cat cat fish") << endl;
cout << !solution.wordPattern("aaaa", "dog cat cat dog") << endl;
cout << !solution.wordPattern("abba", "dog dog dog dog") << endl;
return 0;
}