Word Pattern II
Link
Description
Given a pattern
and a string s
, return true
if s
matches the pattern
.
A string s
matches a pattern
if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern
is replaced by the string it maps to, then the resulting string is s
. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.
Example 1:
- Input:
pattern = "abab", s = "redblueredblue"
- Output:
true
- Explanation: One possible mapping is as follows:
| 'a' -> "red"
'b' -> "blue"
|
Example 2:
- Input:
pattern = "aaaa", s = "asdasdasdasd"
- Output:
true
- Explanation: One possible mapping is as follows:
'a' -> "asd"
Example 3:
- Input:
pattern = "aabb", s = "xyzabcxzyabc"
- Output:
false
Constraints:
1 <= pattern.length, s.length <= 20
pattern
and s
consist of only lowercase English letters.
Solution
| class Solution {
private:
bool backtracking(int pIndex, int sIndex,
const string& pattern, const string& s,
unordered_map<char, string>& patternToWord,
unordered_map<string, char>& wordToPattern) {
if (pIndex == pattern.size() && sIndex == s.size()) return true;
if (pIndex >= pattern.size() || sIndex >= s.size()) return false;
char currentChar = pattern[pIndex];
for (int i = sIndex; i < s.size(); i++) {
string word = s.substr(sIndex, i - sIndex + 1);
if ((patternToWord.count(currentChar) && patternToWord[currentChar] == word)
|| (wordToPattern.count(word) && wordToPattern[word] == currentChar)) {
if (backtracking(pIndex + 1, i + 1, pattern, s, patternToWord, wordToPattern))
return true;
} else if (!patternToWord.count(currentChar) && !wordToPattern.count(word)) {
patternToWord[currentChar] = word;
wordToPattern[word] = currentChar;
if (backtracking(pIndex + 1, i + 1, pattern, s, patternToWord, wordToPattern))
return true;
patternToWord.erase(currentChar);
wordToPattern.erase(word);
}
}
return false;
}
public:
bool wordPatternMatch(string pattern, string s) {
unordered_map<char, string> patternToWord;
unordered_map<string, char> wordToPattern;
return backtracking(0, 0, pattern, s, patternToWord, wordToPattern);
}
};
|