DEV Community

Cover image for 290. Word Pattern Leetcode Problem of The Day- 01 Jan 2023
Priya Srivastava
Priya Srivastava

Posted on

290. Word Pattern Leetcode Problem of The Day- 01 Jan 2023

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (0)