Word pattern ii

Hash Table String Backtracking

48.8% acceptance

Mar 31, 2026

943

Given a pattern and a string s, return true if s matches the pattern. A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

use std::collections::HashMap;

impl Solution {
  pub fn word_pattern_match(pattern: String, s: String) -> bool {
    let pattern: Vec<char> = pattern.chars().collect();
    let s: Vec<char> = s.chars().collect();
    let mut map: HashMap<char, Vec<char>> = HashMap::new();
    let mut used: std::collections::HashSet<Vec<char>> = std::collections::HashSet::new();
    Self::backtrack(&pattern, 0, &s, 0, &mut map, &mut used)
  }

  fn backtrack(
    pattern: &[char], pi: usize,
    s: &[char], si: usize,
    map: &mut HashMap<char, Vec<char>>,
    used: &mut std::collections::HashSet<Vec<char>>,
  ) -> bool {
    if pi == pattern.len() && si == s.len() { return true; }
    if pi == pattern.len() || si == s.len() { return false; }
    let ch = pattern[pi];
    if let Some(mapped) = map.get(&ch).cloned() {
      let len = mapped.len();
      if si + len > s.len() { return false; }
      if s[si..si + len] != mapped[..] { return false; }
      return Self::backtrack(pattern, pi + 1, s, si + len, map, used);
    }
    let remaining_pattern = pattern.len() - pi;
    let remaining_s = s.len() - si;
    for end in si + 1..=s.len() {
      let substr: Vec<char> = s[si..end].to_vec();
      if remaining_s - substr.len() < remaining_pattern - 1 { break; }
      if used.contains(&substr) { continue; }
      map.insert(ch, substr.clone());
      used.insert(substr.clone());
      if Self::backtrack(pattern, pi + 1, s, end, map, used) {
        return true;
      }
      map.remove(&ch);
      used.remove(&substr);
    }
    false
  }
}