Word Pattern

We have all come across word patterns like “ABBA”, “AABB” and so on. We always wonder what this babble could relate to. Today we will try to solve a problem where we try to make use of the babble. A plethora of string problems does not help the case. Given a pattern and a sentence we have to look if the sentence follows the pattern/matches the pattern or not.

Example

Assume that our pattern is “AWWBSW”. So the sentences that follow along the pattern can be

A Big Big Baby Sheep Big

Cat Dog Dog Elephant Ship Dog

To gain a better understanding let us look at the mappings

Explanation

We are thus doing fine as long as we are obeying the mappings

The trouble now boils down to finding a data structure that can help us work with the problem.

Queues, Stacks, and Arrays will find it hard to maintain relationships. Thus, we would go to HashMaps.

HashMaps contain data in the form of key-value pairs and thus look like the ideal choice for the above problem.

Now that we know a bit about our problem let us look into how we are going to do what we are going to do.

• Create a hashmap of all mappings
• Iterate over the string and look over each character and word
  • Look at the character that corresponds to the word from the hashmap
  • If the mapping and the character do not match we return false
• If we do not encounter any mismatches then it is sure that we have found just the perfect match!

Let us look at the code

Java Code For Word Mapping

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

C++ Code For Word Mapping

class Solution 
{
public:
    bool wordPattern(string pattern, string str) 
    {
    std::string w;                 
    std::stringstream ss(str);
    std::vector<std::string> words; 

    while (ss >> w)
    {
        words.push_back(w);
    }
        
    if(words.size() != pattern.size()) 
        return false;
    
    map<char,string> a;
    map<string,char> b;
    
    for(int i = 0; i < words.size(); i++)
    {
        a[pattern[i]] = words[i];
        b[words[i]] = pattern[i];
    }
    
    for(int i = 0; i < words.size(); i++)
    {
        if(a[pattern[i]] != words[i] || b[words[i]] != pattern[i])
        {
            return false;
        }
    }
     
    return true;
   }
};

Complexity Analysis

Time complexity: O(n)

Space Complexity: O(n)

Why?

Let us assume that the string provided to us has 5 words. (Not taking into account repetitions as of now)

• We will loop over the string
• Each word will map to each pattern in the string.
  • Thus, the hashmap that will be created will be of the same size i.e 5
• Let us assume that one of the words appears twice. Relevant words reduce to 4.
  • If the hashmap shall be of a greater size we are definitely breaking the rule.
  • Thus the space complexity is O(n)
• We go over each and every word once. Which makes the number of iterations incurred 5
• This makes the time complexity as linear/O(n)

Thus was a tiny overview of how to make sense out of babble patterns and match them out!

References