Strings - Word Pattern

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.

Input: pattern = "abba", s = "dog cat cat dog"
Output: true
Explanation: here 'a' can be mapped to 'dog' and 'b' can be mapped to 'cat' and vice versa.

Input: pattern = "abba", s = "dog cat cat fish"
Output: false
Explanation: 'a' has two different mappins, so it is not following the pattern.

Input: pattern = "abba", s = "cat cat cat cat"
Output: false
Explanation: here both 'a' and 'b' mapped to same words, so it is not following the pattern.

Solution 1 - store mapping of each letter to word and word to letter in HashMaps

In this approach, we are going to store mapping of letters of pattern to words in s into a HashMap and from word to letter into another HashMap. The reason why we do this is because we need to check no two letters mapped to same word (as shown is example 3 above) to.

Implementation details

We will create two different HashMaps to store mappings of letters to words and words to letters.
As a first step we will spli the input string s with regular expression ' ' (space separated) that returns words in the string as an array. String[] words = s.split(" ");
In the next step, we will check whether number of characters in pattern string are equal to number of words s, if they are not equal then we will return false as string s is not following the pattern string.
Now for each letter at index i in pattern string, store corresponding mapped index from words array into one HashMap, and also store mapping from word to the character, the reason why we do this is because to check if different letters in pattern string are pointing to same word or not, if it is then we can return false.
If mappings from letters from pattern string to words and vice versa, then we can return true.

import java.util.HashMap; public class WordPattern { static boolean usingHashMapToStoreMapping(String pattern, String s) { String[] words = s.split(" "); if(pattern.length() != words.length) { return false; } HashMap<Character, String> map_c_word = new HashMap<>(); HashMap<String, Character> map_word_c = new HashMap<>(); for(int i=0; i<pattern.length(); i++) { char c = pattern.charAt(i); String wordValAfter = map_c_word.putIfAbsent(c, words[i]); if(wordValAfter != null && !wordValAfter.equals(words[i])) { return false; } Character cValAfter = map_word_c.putIfAbsent(words[i], c); if(cValAfter != null && !cValAfter.equals(c)){ return false; } } return true; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input string pattern length.
Space complexity: O(m* n) since we are storing all words from string s and m is the average length of a word.

Above implementations source code can be found at GitHub link for Java code

Contents

Implementation details

Complexity Analysis: