Word Pattern Given a pattern
and a string s
, find if s
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 s
.
Example 1:
Input: pattern = "abba", s = "dog cat cat dog" Output: true
Example 2:
Input: pattern = "abba", s = "dog cat cat fish" Output: false
Example 3:
Input: pattern = "aaaa", s = "dog cat cat dog" Output: false
Constraints:
1 <= pattern.length <= 300
pattern
contains only lower-case English letters.1 <= s.length <= 3000
s
contains only lowercase English letters and spaces' '
.s
does not contain any leading or trailing spaces.- All the words in
s
are separated by a single space.
Word Pattern Solutions
✅Time: O(n)
✅Space: O(n)
C++
class Solution {
public:
bool wordPattern(string pattern, string str) {
const int n = pattern.length();
istringstream iss(str);
vector<int> charToIndex(128);
unordered_map<string, int> stringToIndex;
int i = 0;
for (string word; iss >> word; ++i) {
if (i == n) // out of bound
return false;
if (charToIndex[pattern[i]] != stringToIndex[word])
return false;
charToIndex[pattern[i]] = i + 1;
stringToIndex[word] = i + 1;
}
return i == n;
}
};
Java
class Solution {
public boolean wordPattern(String pattern, String str) {
String[] words = str.split(" ");
if (words.length != pattern.length())
return false;
Map<Character, Integer> charToIndex = new HashMap<>();
Map<String, Integer> stringToIndex = new HashMap<>();
for (Integer i = 0; i < pattern.length(); ++i)
if (charToIndex.put(pattern.charAt(i), i) != stringToIndex.put(words[i], i))
return false;
return true;
}
}
Python
class Solution:
def wordPattern(self, pattern: str, str: str) -> bool:
t = str.split()
return [*map(pattern.index, pattern)] == [*map(t.index, t)]
Watch Tutorial
Checkout more Solutions here