290. Word Pattern Leetcode Solution
Word Pattern Leetcode Problem :
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.
Word Pattern Leetcode Solution :
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.
Example 1:
- Input: pattern = “abba”, s = “dog cat cat fish”
- Output: false
Example 2:
- Input: pattern = “aaaa”, s = “dog cat cat dog”
- Output: false
Observation :
-Length should be same, if not then its not possible
-we have to map the character with the the string
-if any other value for this key, we have to return false
Approach :
-To map the Character with the String we have to use the Map
-Put the Character with String if not present
-if Its present then see, whether this key value are same or not, if not same then return the false but,
-if the value that we are adding is already had seen or use or other key value, then return false, hence we use the hashset of strings
Prime Course Trailer
Related Banners
Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription
Code :
class Solution {
public:
bool wordPattern(string pattern, string s) {
map< char, string> dict;
map< string, char> dict2;
int i = 0;
int j = 0;
string w = "";
for (i = 0; i < pattern.length(); i++) {
w = "";
if (j >= s.length() && i < pattern.length()) {
return(false);
}
while (s[j] != ' ' && j < s.length()) {
w += s[j];
j++;
}
j++;
if (dict2.contains(w) && dict2[w] != pattern[i]) {
return(false);
} else if (!dict2.contains(w)) {
if (dict.contains(pattern[i])) {
return(false);
} else {
dict[pattern[i]] = w;
dict2[w] = pattern[i];
}
}
}
if (j < s.length()+1) {
return(false);
}
return(true);
}
};
class Solution {
public boolean wordPattern(String pattern, String s) {
Map< Character, String> map = new HashMap< >();
String word[] = s.trim().split(" ");
Set< String> set = new HashSet< >();
if(pattern.length() != word.length) return false;
for(int i = 0; i < pattern.length(); i++){
char ch = pattern.charAt(i);
if(map.containsKey(ch)){
String str = map.get(ch);
if(str.equals(word[i]) == false) return false;
}else{
if(set.contains(word[i])==false){
map.put(ch, word[i]);
set.add(word[i]);
}else{
return false;
}
}
}
return true;
}
}
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
pattern_to_s = {} # Mapping from pattern to s
s_to_pattern = {} # Mapping from s to pattern
s_words = s.split()
if len(pattern) != len(s_words):
return False
for i in range(len(s_words)):
char_s = s_words[i]
char_pattern = pattern[i]
# Check if there is a mapping in both dictionaries
if char_pattern in pattern_to_s:
if pattern_to_s[char_pattern] != char_s:
return False
else:
pattern_to_s[char_pattern] = char_s
if char_s in s_to_pattern:
if s_to_pattern[char_s] != char_pattern:
return False
else:
s_to_pattern[char_s] = char_pattern
return True
Get over 200+ course One Subscription
Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others
Login/Signup to comment