Hello everyone! It is New year's first day and I have decided to document the questions I solve on Leetcode. This is to keep a record of my thought process of approaching questions and also to document my solutions in an organised manner.
If you are reading this, hope the blog helps you as well. So here is how I approached the first question of Leetcode daily challenge.
Question link:
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
Intuition
The problem states there are 2 strings and all I have to do is compare them such that every character of 'pattern' corresponds to the 'word' of String 's'.
eg:
a -> dog
b -> cat
b -> cat
a -> dog
(And vice versa)
This statements brings us to the idea that we can use a hashmap to store word and character as key and value.
Approach
All we need to do is map the word of s to the char of pattern and vice versa. Check if they correspond to the same thing using .equals()
Base case: the length of pattern and number of words in s should be same.
Now code this!
How will I get the word? By using .split(" ")
Complexity
-
Time complexity:
O(n)
-
Space complexity:
O(n)
Code
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] word = s.split(" ");
if(word.length != pattern.length()) return false;
HashMap<Character, String> map1 = new HashMap<>();
HashMap<String, Character> map2 = new HashMap<>();
for(int i=0; i<pattern.length(); i++) {
char c = pattern.charAt(i);
String w = word[i];
if(!map1.containsKey(c)){
map1.put(c, w);
}
if(!map2.containsKey(w)) {
map2.put(w, c);
}
if( (!map1.get(c).equals(w)) || (!map2.get(w).equals(c)) )
return false;
}
return true;
}
}
Top comments (0)