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
Example 4:
Input: pattern = "abba", s = "dog dog dog dog" Output: false
Constraints:
1 <= pattern.length <= 300patterncontains only lower-case English letters.1 <= s.length <= 3000scontains only lower-case English letters and spaces' '.sdoes not contain any leading or trailing spaces.- All the words in
sare separated by a single space.
class Solution {
public boolean wordPattern(String pattern, String s) {
HashMap index = new HashMap();
String[] words = s.split(" ");
if (words.length != pattern.length())
return false;
for (Integer i = 0; i < words.length; i++) {
char c = pattern.charAt(i);
String w = words[i];
if (!index.containsKey(c))
index.put(c, i);
if (!index.containsKey(w))
index.put(w, i);
if (index.get(c) != index.get(w))
return false;
}
return true;
}
}
Here, we are going to solve using Hashmap which stores both pattern and words as key and those indexes as value.
1) If words and pattern length are different, return false.
2) Store each character and words into index map, with its indexes as value. If keys are already present no need to update.
3) If values(i.e., index) of both pattern and word are different, then return false. Using this, we can easily find an irregular pattern.
4) If entire loop completes, return true.
Comments
Post a Comment