291. Word Pattern II

leetcode medium

#csharp#hash-table#leetcode#medium#recursion#string#tree

Task

Дан шаблон и строка s, вернуть true, если строка s соответствует шаблону.

Строка s соответствует шаблону, если существует биективное отображение отдельных символов на непустые строки так, что если каждый символ в шаблоне заменить на строку, которой он отображается, то результирующая строка будет равна s. Биективное отображение означает, что ни два символа не отображаются на одну и ту же строку, и ни один символ не отображается на две разные строки.

Пример:

Input: pattern = "abab", s = "redblueredblue"

Output: true

Explanation: One possible mapping is as follows:

'a' -> "red"

'b' -> "blue"

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public bool WordPatternMatch(string pattern, string s) {
        var symbolMap = new Dictionary<char, string>();
        var wordSet = new HashSet<string>();
        return IsMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }
    private bool IsMatch(string s, int sIndex, string pattern, int pIndex,
                         Dictionary<char, string> symbolMap, HashSet<string> wordSet) {
        if (pIndex == pattern.Length) {
            return sIndex == s.Length;
        }
        char symbol = pattern[pIndex];
        if (symbolMap.ContainsKey(symbol)) {
            string word = symbolMap[symbol];
            if (!s.Substring(sIndex).StartsWith(word)) {
                return false;
            }
            return IsMatch(s, sIndex + word.Length, pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.Length; k++) {
            string newWord = s.Substring(sIndex, k - sIndex);
            if (wordSet.Contains(newWord)) {
                continue;
            }
            symbolMap[symbol] = newWord;
            wordSet.Add(newWord);
            if (IsMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.Remove(symbol);
            wordSet.Remove(newWord);
        }
        return false;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool WordPatternMatch(string pattern, string s) {
        var symbolMap = new unordered_map<char, string>();
        var wordSet = new HashSet<string>();
        return IsMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }
    private bool IsMatch(string s, int sIndex, string pattern, int pIndex,
                         unordered_map<char, string> symbolMap, HashSet<string> wordSet) {
        if (pIndex == pattern.size()) {
            return sIndex == s.size();
        }
        char symbol = pattern[pIndex];
        if (symbolMap.count(symbol)) {
            string word = symbolMap[symbol];
            if (!s.Substring(sIndex).StartsWith(word)) {
                return false;
            }
            return IsMatch(s, sIndex + word.size(), pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.size(); k++) {
            string newWord = s.Substring(sIndex, k - sIndex);
            if (wordSet.Contains(newWord)) {
                continue;
            }
            symbolMap[symbol] = newWord;
            wordSet.push_back(newWord);
            if (IsMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.Remove(symbol);
            wordSet.Remove(newWord);
        }
        return false;
    }
}

Java solution

matched/original

import java.util.HashMap;
import java.util.HashSet;

public class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        HashMap<Character, String> symbolMap = new HashMap<>();
        HashSet<String> wordSet = new HashSet<>();
        return isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    private boolean isMatch(String s, int sIndex, String pattern, int pIndex,
                            HashMap<Character, String> symbolMap, HashSet<String> wordSet) {
        if (pIndex == pattern.length()) {
            return sIndex == s.length();
        }
        char symbol = pattern.charAt(pIndex);
        if (symbolMap.containsKey(symbol)) {
            String word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return isMatch(s, sIndex + word.length(), pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (int k = sIndex + 1; k <= s.length(); k++) {
            String newWord = s.substring(sIndex, k);
            if (wordSet.contains(newWord)) {
                continue;
            }
            symbolMap.put(symbol, newWord);
            wordSet.add(newWord);
            if (isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.remove(symbol);
            wordSet.remove(newWord);
        }
        return false;
    }
}

JavaScript solution

matched/original

class Solution {
    wordPatternMatch(pattern, s) {
        const symbolMap = new Map();
        const wordSet = new Set();
        return this.isMatch(s, 0, pattern, 0, symbolMap, wordSet);
    }

    isMatch(s, sIndex, pattern, pIndex, symbolMap, wordSet) {
        if (pIndex
        if (pIndex === pattern.length) {
            return sIndex === s.length;
        }
        const symbol = pattern[pIndex];
        if (symbolMap.has(symbol)) {
            const word = symbolMap.get(symbol);
            if (!s.startsWith(word, sIndex)) {
                return false;
            }
            return this.isMatch(s, sIndex + word.length, pattern, pIndex + 1, symbolMap, wordSet);
        }
        for (let k = sIndex + 1; k <= s.length; k++) {
            const newWord = s.substring(sIndex, k);
            if (wordSet.has(newWord)) {
                continue;
            }
            symbolMap.set(symbol, newWord);
            wordSet.add(newWord);
            if (this.isMatch(s, k, pattern, pIndex + 1, symbolMap, wordSet)) {
                return true;
            }
            symbolMap.delete(symbol);
            wordSet.delete(newWord);
        }
        return false;
    }
}

Python solution

matched/original

class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        symbol_map = {}
        word_set = set()
        return self.is_match(s, 0, pattern, 0, symbol_map, word_set)

    def is_match(self, s, s_index, pattern, p_index, symbol_map, word_set):
        if p_index == len(pattern):
            return s_index == len(s)
        
        symbol = pattern[p_index]
        if symbol in symbol_map:
            word = symbol_map[symbol]
            if not s.startswith(word, s_index):
                return False
            return self.is_match(s, s_index + len(word), pattern, p_index + 1, symbol_map, word_set)

        for k in range(s_index + 1, len(s) + 1):
            new_word = s[s_index:k]
            if new_word in word_set:
                continue
            symbol_map[symbol] = new_word
            word_set.add(new_word)
            if self.is_match(s, k, pattern, p_index + 1, symbol_map, word_set):
                return True
            del symbol_map[symbol]
            word_set.remove(new_word)
        
        return False

Go solution

matched/original

package main

func wordPatternMatch(pattern string, s string) bool {
    symbolMap := make(map[rune]string)
    wordSet := make(map[string]bool)
    return isMatch(s, 0, pattern, 0, symbolMap, wordSet)
}

func isMatch(s string, sIndex int, pattern string, pIndex int,
    symbolMap map[rune]string, wordSet map[string]bool) bool {
    if pIndex == len(pattern) {
        return sIndex == len(s)
    }
    symbol := rune(pattern[pIndex])
    if word, ok := symbolMap[symbol]; ok {
        if !startsWith(s, sIndex, word) {
            return false
        }
        return isMatch(s, sIndex+len(word), pattern, pIndex+1, symbolMap, wordSet)
    }
    for k := sIndex + 1; k <= len(s); k++ {
        newWord := s[sIndex:k]
        if wordSet[newWord] {
            continue
        }
        symbolMap[symbol] = newWord
        wordSet[newWord] = true
        if isMatch(s, k, pattern, pIndex+1, symbolMap, wordSet) {
            return true
        }
        delete(symbolMap, symbol)
        delete(wordSet, newWord)
    }
    return false
}

func startsWith(s string, sIndex int, word string) bool {
    if len(s)-sIndex < len(word) {
        return false
    }
    for i := 0; i < len(word); i++ {
        if s[sIndex+i] != word[i] {
            return false
        }
    }
    return true
}

Explanation

Algorithm

Инициализация структур данных и определение рекурсивной функции:

Создайте хеш-таблицу symbolMap для отображения символов шаблона на подстроки строки s.

Создайте множество wordSet для хранения уникальных подстрок строки s, которые были отображены на символ.

Определите рекурсивную функцию isMatch, принимающую индексы в строке s (sIndex) и в шаблоне (pIndex), чтобы определить, соответствует ли строка s шаблону.

Рекурсивная проверка соответствия:

Базовый случай: если pIndex равно длине шаблона, верните true, если sIndex равно длине строки s; иначе верните false.

Получите символ из шаблона по индексу pIndex.

Если символ уже ассоциирован с подстрокой, проверьте, совпадают ли следующие символы в строке s с этой подстрокой. Если нет, верните false. Если совпадают, вызовите isMatch для следующего символа в шаблоне.

Отображение новых подстрок:

Если символ новый, попробуйте сопоставить его с новыми подстроками строки s, начиная с sIndex и до конца строки.

Для каждой новой подстроки проверьте, существует ли она уже в `

😎