Word Pattern I and II

XXX. Word Pattern and Word Pattern Matching

Hash Map

Backtracking

Problem Statement:

Word Pattern: Given a pattern and a string str, find if str follows the same pattern. Each character in the pattern maps to a word in str uniquely.

Word Pattern Matching: Given a pattern and a string str, determine if the pattern can be mapped to str such that each character in the pattern maps to a substring in str uniquely.

Algorithm:

Word Pattern:

1. Split the string str into an array of words using space as a delimiter.
2. Check if the length of the pattern matches the number of words in str. If not, return false.
3. Use a hash map to store the mapping of pattern characters to words and a set to track used words.
4. For each character in the pattern:
   • If the character is already mapped, check if the word matches the mapped word. If not, return false.
   • If the character is not mapped but the word is already in the set, return false.
   • Otherwise, add the mapping and the word to the set.

Word Pattern Matching:

1. Use a backtracking approach to explore all possible mappings:
• If the pattern is exhausted and the string is also exhausted, return true.
• If either the pattern or the string is exhausted, return false.
• For each substring of the string:
  • If the character is already mapped, check if the substring matches the mapped substring.
  • If the character is not mapped and the substring is not already used, map the character to the substring and recurse for the remaining pattern and string.

Complexity:

Word Pattern:
Time Complexity: O(n), where n is the length of the string.
Space Complexity: O(n) for the hash map and set.

Word Pattern Matching:
Time Complexity: O(n * m), where n is the length of the pattern and m is the length of the string.
Space Complexity: O(n + m) for the hash map and set.

Java Implementation:

public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    Map map = new HashMap<>();
    Set set = new HashSet<>();

    if (pattern.length() != words.length) return false;

    for (int i = 0; i < words.length; i++) {
        char c = pattern.charAt(i);
        String word = words[i];

        if (map.containsKey(c)) {
            if (!map.get(c).equals(word)) return false; // Character already mapped
        } else {
            if (set.contains(word)) return false; // Word already used
            map.put(c, word);
            set.add(word);
        }
    }
    return true;
}

public boolean wordPatternMatch(String pattern, String str) {
    Map map = new HashMap<>();
    Set set = new HashSet<>();
    return backtrack(pattern, str, 0, 0, map, set);
}

public boolean backtrack(String pattern, String str, int index, int start, Map map, Set set) {
    if (index == pattern.length() && start == str.length()) return true;
    if (index == pattern.length() || start == str.length()) return false;

    char c = pattern.charAt(index);

    for (int i = start; i < str.length(); i++) {
        String sub = str.substring(start, i + 1);

        if (map.containsKey(c)) {
            if (map.get(c).equals(sub)) 
                if (backtrack(pattern, str, index + 1, i + 1, map, set)) return true;
            
        } else if (!set.contains(sub)) {
            map.put(c, sub);
            set.add(sub);
            if (backtrack(pattern, str, index + 1, i + 1, map, set)) return true;
            map.remove(c);
            set.remove(sub);
        }
    }
    return false;
}
                

Python Implementation:

def wordPattern(pattern, s):
    words = s.split()
    char_to_word = {}
    used_words = set()

    if len(pattern) != len(words):
        return False

    for c, word in zip(pattern, words):
        if c in char_to_word:
            if char_to_word[c] != word:
                return False
        else:
            if word in used_words:
                return False
            char_to_word[c] = word
            used_words.add(word)

    return True

def wordPatternMatch(pattern, s):
    def backtrack(index, start):
        if index == len(pattern) and start == len(s):
            return True
        if index == len(pattern) or start == len(s):
            return False

        char = pattern[index]

        for i in range(start, len(s)):
            sub = s[start:i + 1]

            if char in char_to_word:
                if char_to_word[char] == sub:
                    if backtrack(index + 1, i + 1):
                        return True
            elif sub not in used_words:
                char_to_word[char] = sub
                used_words.add(sub)
                if backtrack(index + 1, i + 1):
                    return True
                del char_to_word[char]
                used_words.remove(sub)

        return False

    char_to_word = {}
    used_words = set()
    return backtrack(0, 0)
                

C++ Implementation:

#include 
#include 
#include 
using namespace std;

bool wordPattern(string pattern, string s) {
    vector words;
    string word;
    stringstream ss(s);
    while (ss >> word) words.push_back(word);

    if (pattern.size() != words.size()) return false;

    unordered_map charToWord;
    unordered_set usedWords;

    for (int i = 0; i < pattern.size(); ++i) {
        char c = pattern[i];
        if (charToWord.count(c)) {
            if (charToWord[c] != words[i]) return false;
        } else {
            if (usedWords.count(words[i])) return false;
            charToWord[c] = words[i];
            usedWords.insert(words[i]);
        }
    }
    return true;
}

bool wordPatternMatch(string pattern, string s) {
    function backtrack = [&](int index, int start) {
        if (index == pattern.size() && start == s.size()) return true;
        if (index == pattern.size() || start == s.size()) return false;

        char c = pattern[index];

        for (int i = start; i < s.size(); ++i) {
            string sub = s.substr(start, i - start + 1);

            if (charToWord.count(c)) {
                if (charToWord[c] == sub) {
                    if (backtrack(index + 1, i + 1)) return true;
                }
            } else if (!usedWords.count(sub)) {
                charToWord[c] = sub;
                usedWords.insert(sub);
                if (backtrack(index + 1, i + 1)) return true;
                charToWord.erase(c);
                usedWords.erase(sub);
            }
        }
        return false;
    };

    unordered_map charToWord;
    unordered_set usedWords;
    return backtrack(0, 0);
}