Word Pattern LeetCode Solution

Difficulty Level Medium
Frequently asked in Amazon Apple Capital One Dropbox Facebook GoDaddy Microsoft Uber
BoltViews 6961

Problem Statement

Word Pattern LeetCode Solution – We are given 2 strings – “s” and “pattern”, we need to find if the pattern follows s. Follows here means full match. More formally, we can for every pattern[i] there should only be one s[i] and vice versa i.e. there is a bijection between a letter in a pattern and a non-empty word in s.

Examples and Explanation

Example 1:

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation:
a -> dog
b -> cat

Example 2:

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation:
a -> dog
b -> cat
pattern[3] = a which corresponds to s[0], dog defined earlier, but s[3] has no dog

Example 3:

Input: pattern = "aaaa", s = "dog cat cat dog"
Output: false
Explanation:
a -> dog
Two different a are defined, i.e. dog and cat

Approach

We will map the words in s to their corresponding letters in the pattern. If pattern[i] already exists, then check if s[i] is equal to pattern[i]. To map pattern[i] and worlds in “s”, let’s use hashmaps.

Since the words are given through a single string s, we can define another array of strings to store all the words for easy implementation. Iterate through the string s, if there is space, push the word into our string array.

Code

C++ Code for Word Pattern LeetCode

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        map<char,string> cnt;
        vector<string> words;
        string t="";
        for(int i=0; i<=s.size(); i++) {
            if(s[i] == '\0') {
                words.push_back(t);
                break;
            }
            else if(s[i] == ' ') {
                words.push_back(t);
                t="";
            }
            else t+=s[i];
            
        }
        
        if(words.size() != pattern.size()) return 0;
        
        map<string, int> vis; // vis = visited
        for(int i=0; i<pattern.size(); i++) {
            // pattern already exists
            if(cnt.find(pattern[i]) != cnt.end()) {
                if(cnt[pattern[i]] != words[i]) return 0;
                
                
            }
            else {
                cnt[pattern[i]] =  words[i];
                if(vis[words[i]]) return 0;
                vis[words[i]] = 1;
            }
        }
        return 1;
    }
};

Java Code for Word Pattern LeetCode

class Solution {
    public boolean wordPattern(String pattern, String s) {
        Map<Character,String> m=new HashMap<>();
        String words[]=s.split(" ");
        
        if(pattern.length()!=words.length) return false;
        
        int n = words.length;
        for(int i=0;i<n;i++){
            
            char c= pattern.charAt(i);
            
            if(m.containsKey(c)){
                if(!words[i].equals(m.get(c))) return false;
            }
            else{
                if(m.containsValue(words[i])){
                    return false;
                }
                m.put(c, words[i]);
            }
        }
        return true;
    }
}

Complexity Analysis for Word Pattern LeetCode Solution

  • Time complexity: O(N)
  • Space complexity: O(M)
    • M represents the number of unique words in s. Although there are 2 hashmaps there can be at most 26 keys, hence space complexity of the map is constant.

Reference: https://en.wikipedia.org/wiki/Pattern_matching

Translate »