algorithms►leetcode

019-子结构判断

子结构判断

子结构判断是算法设计中常见的问题类型，主要用于确定一个结构是否包含在另一个结构中

1. 字符串子序列判断

问题描述

判断字符串s是否是字符串t的子序列（子序列可以不连续但顺序必须一致）

解法（双指针法）

1
2
3
4
5
6
7
8
9
10
function isSubsequence(s, t) {
    let i = 0, j = 0;
    while (i < s.length && j < t.length) {
        if (s[i] === t[j]) {
            i++;
        }
        j++;
    }
    return i === s.length;
}

复杂度分析

  • 时间复杂度：O(n)
  • 空间复杂度：O(1)

2. LCR143.树的子树判断

问题描述

给定两棵二叉树 tree1 和 tree2，判断 tree2 是否以 tree1 的某个节点为根的子树具有相同的结构和节点值 。 注意，空树不会是以 tree1 的某个节点为根的子树具有相同的结构和节点值 。

解法（递归+DFS）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isSubtree(root, subRoot) {
    if (!root) return false;
    return isSameTree(root, subRoot) || 
           isSubtree(root.left, subRoot) || 
           isSubtree(root.right, subRoot);
}

function isSameTree(p, q) {
    if (!p && !q) return true;
    if (!p || !q) return false;
    return p.val === q.val && 
           isSameTree(p.left, q.left) && 
           isSameTree(p.right, q.right);
}

复杂度分析

  • 时间复杂度：O(mn)，m和n分别是两树的节点数
  • 空间复杂度：O(h)，h为树的高度

3. 数组子数组判断

问题描述

判断数组subArr是否是数组arr的连续子数组

解法（滑动窗口）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isSubarray(arr, subArr) {
    const n = arr.length, m = subArr.length;
    if (m > n) return false;
    
    for (let i = 0; i <= n - m; i++) {
        let match = true;
        for (let j = 0; j < m; j++) {
            if (arr[i + j] !== subArr[j]) {
                match = false;
                break;
            }
        }
        if (match) return true;
    }
    return false;
}

优化解法（KMP算法）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
function isSubarrayKMP(arr, subArr) {
    // 构建部分匹配表
    function buildLPS(pattern) {
        const lps = [0];
        let len = 0, i = 1;
        while (i < pattern.length) {
            if (pattern[i] === pattern[len]) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len !== 0) {
                    len = lps[len - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    const lps = buildLPS(subArr);
    let i = 0, j = 0;
    while (i < arr.length) {
        if (arr[i] === subArr[j]) {
            i++;
            j++;
            if (j === subArr.length) return true;
        } else {
            if (j !== 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return false;
}

复杂度分析

  • 滑动窗口：O(mn)
  • KMP算法：O(m+n)

4. 图的子图判断

问题描述

判断图H是否是图G的子图（同构问题）

解法（回溯法）

1
2
3
4
5
6
7
8
9
10
11
12
function isSubgraph(G, H) {
    // 简化版实现思路
    // 1. 检查顶点数和边数
    if (H.vertices.length > G.vertices.length) return false;
    if (H.edges.length > G.edges.length) return false;
    
    // 2. 尝试所有可能的顶点映射
    // 实际实现需要使用回溯算法尝试所有可能的映射
    // 这里省略具体实现代码
    
    return backtrackingCheck(G, H);
}

5. 常见问题变种

变种1：判断子序列出现次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function numDistinct(s, t) {
    const m = s.length, n = t.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
    
    for (let i = 0; i <= m; i++) dp[i][0] = 1;
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (s[i-1] === t[j-1]) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    
    return dp[m][n];
}

变种2：带通配符的子序列匹配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function isMatch(s, p) {
    const m = s.length, n = p.length;
    const dp = Array.from({length: m+1}, () => new Array(n+1).fill(false));
    dp[0][0] = true;
    
    for (let j = 1; j <= n; j++) {
        if (p[j-1] === '*') {
            dp[0][j] = dp[0][j-1];
        }
    }
    
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (p[j-1] === s[i-1] || p[j-1] === '?') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] === '*') {
                dp[i][j] = dp[i][j-1] || dp[i-1][j];
            }
        }
    }
    
    return dp[m][n];
}

总结

子结构判断问题的核心在于：

  1. 明确子结构的定义（连续/非连续）
  2. 选择合适的算法策略（双指针、动态规划、回溯等）
  3. 考虑边界条件和优化空间

不同场景下的子结构判断需要采用不同的方法，理解各种数据结构的特性是解决这类问题的关键。