Word Patterns | Interview Question at Mastercard

Introduction: In the world of string manipulation, unraveling patterns and matching sequences play a pivotal role in various applications. In this tutorial, we’ll embark on a journey to decode word patterns, where we’ll determine if two strings follow the same pattern. Through the lens of Java programming, we’ll explore an efficient approach to tackle this challenge.

Problem Statement: Given two strings, ‘S’ and ‘T’, our objective is to ascertain if ‘S’ follows the same pattern as ‘T’. Here, following the pattern entails a bijection between each character of ‘T’ and a non-empty word of ‘S’.

Understanding the Approach: To solve this problem, we’ll employ a HashMap to map characters from ‘T’ to corresponding words in ‘S’. We’ll iterate through each character in ‘T’ and verify if the mapped word from ‘S’ aligns with the current word in ‘S’. If they match, we continue the process. If they don’t, we conclude that ‘S’ does not follow the same pattern as ‘T’.

Algorithm Overview:

1. Split string ‘S’ into individual words.
2. Check if the number of characters in ‘T’ matches the number of words in ‘S’. If not, return “No”.
3. Initialize a HashMap to map characters from ‘T’ to words in ‘S’.
4. Iterate through each character in ‘T’ and word in ‘S’:
   • If the character exists in the HashMap:
     • Check if the mapped word matches the current word in ‘S’. If not, return “No”.
   • If the character doesn’t exist in the HashMap:
     • Check if the word is already mapped to another character. If yes, return “No”.
     • Add the character-word mapping to the HashMap.
5. If the iteration completes without any mismatches, return “Yes”.

Implementation in Java:

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        // Example usage:
        String S = "lion cow cow lion";
        String T = "wccw";
        System.out.println(wordPattern(S, T));  // Output: Yes
    }

    public static String wordPattern(String S, String T) {
        String[] words = S.split(" ");
        
        if (T.length() != words.length) {
            return "No";
        }
        
        HashMap<Character, String> map = new HashMap<>();
        
        for (int i = 0; i < T.length(); i++) {
            char c = T.charAt(i);
            String word = words[i];
            
            if (map.containsKey(c)) {
                if (!map.get(c).equals(word)) {
                    return "No";
                }
            } else {
                if (map.containsValue(word)) {
                    return "No";
                }
                map.put(c, word);
            }
        }
        
        return "Yes";
    }
}
Code language: Java (java)

Conclusion: By leveraging HashMaps and iterative processing, we’ve deciphered the intricate patterns between two strings. This approach empowers us to efficiently match characters and words, shedding light on the alignment between string sequences. With this newfound knowledge, you’re equipped to tackle similar string matching challenges with confidence. Happy matching!