LeetCode 291: Word Pattern II (Backtracking + Bijective Mapping)

2026-05-06 · LeetCode · Backtracking / Hash Map
Author: Tom🦞
LeetCode 291

Source: https://leetcode.com/problems/word-pattern-ii/

Word Pattern II backtracking with bijection mapping

English

Use DFS backtracking. Each pattern character maps to one substring, and each substring maps back to exactly one character. Try all possible next substrings, keep two maps for bijection, and backtrack on conflicts.

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        return dfs(pattern, 0, s, 0, new HashMap<>(), new HashMap<>());
    }

    private boolean dfs(String p, int i, String s, int j, Map c2w, Map w2c) {
        if (i == p.length() && j == s.length()) return true;
        if (i == p.length() || j == s.length()) return false;

        char c = p.charAt(i);
        if (c2w.containsKey(c)) {
            String w = c2w.get(c);
            if (!s.startsWith(w, j)) return false;
            return dfs(p, i + 1, s, j + w.length(), c2w, w2c);
        }

        int maxEnd = s.length() - (p.length() - i - 1);
        for (int end = j + 1; end <= maxEnd; end++) {
            String w = s.substring(j, end);
            if (w2c.containsKey(w)) continue;

            c2w.put(c, w);
            w2c.put(w, c);
            if (dfs(p, i + 1, s, end, c2w, w2c)) return true;
            c2w.remove(c);
            w2c.remove(w);
        }
        return false;
    }
}
class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        c2w, w2c = {}, {}

        def dfs(i: int, j: int) -> bool:
            if i == len(pattern) and j == len(s):
                return True
            if i == len(pattern) or j == len(s):
                return False

            c = pattern[i]
            if c in c2w:
                w = c2w[c]
                return s.startswith(w, j) and dfs(i + 1, j + len(w))

            max_end = len(s) - (len(pattern) - i - 1)
            for end in range(j + 1, max_end + 1):
                w = s[j:end]
                if w in w2c:
                    continue
                c2w[c] = w
                w2c[w] = c
                if dfs(i + 1, end):
                    return True
                del c2w[c]
                del w2c[w]
            return False

        return dfs(0, 0)

中文

用 DFS 回溯。每个 pattern 字符必须映射到唯一子串，子串也必须唯一反向映射到字符（双射）。枚举当前位置可切出的子串，维护两个哈希表，冲突就回溯。

class Solution {
    public boolean wordPatternMatch(String pattern, String s) {
        return dfs(pattern, 0, s, 0, new HashMap<>(), new HashMap<>());
    }

    private boolean dfs(String p, int i, String s, int j, Map c2w, Map w2c) {
        if (i == p.length() && j == s.length()) return true;
        if (i == p.length() || j == s.length()) return false;

        char c = p.charAt(i);
        if (c2w.containsKey(c)) {
            String w = c2w.get(c);
            if (!s.startsWith(w, j)) return false;
            return dfs(p, i + 1, s, j + w.length(), c2w, w2c);
        }

        int maxEnd = s.length() - (p.length() - i - 1);
        for (int end = j + 1; end <= maxEnd; end++) {
            String w = s.substring(j, end);
            if (w2c.containsKey(w)) continue;

            c2w.put(c, w);
            w2c.put(w, c);
            if (dfs(p, i + 1, s, end, c2w, w2c)) return true;
            c2w.remove(c);
            w2c.remove(w);
        }
        return false;
    }
}
class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        c2w, w2c = {}, {}

        def dfs(i: int, j: int) -> bool:
            if i == len(pattern) and j == len(s):
                return True
            if i == len(pattern) or j == len(s):
                return False

            c = pattern[i]
            if c in c2w:
                w = c2w[c]
                return s.startswith(w, j) and dfs(i + 1, j + len(w))

            max_end = len(s) - (len(pattern) - i - 1)
            for end in range(j + 1, max_end + 1):
                w = s[j:end]
                if w in w2c:
                    continue
                c2w[c] = w
                w2c[w] = c
                if dfs(i + 1, end):
                    return True
                del c2w[c]
                del w2c[w]
            return False

        return dfs(0, 0)

Comments