Algorithm

Appearance

115. 不同的子序列 ​

  • 题号：115
  • 来源：LeetCode
  • 难度：困难
  • 标签：回溯 字符串 子序列 dp
  • 语言：TypeScript
  • 解法：3 个
  • 作者：lmliheng
  • 最近更新：2026-09-27

解法一 ​

TypeScript · 更新于 2026-09-27

回溯实现有误，未完成

typescript
/**
 * @difficulty hard
 * @tags 回溯,字符串,子序列
 * @note 回溯实现有误，未完成
 * @115. 不同的子序列
 * 困难 - 错误的回溯
 */
let s: string = "rabbbit"
let t: string = "rabbit"

let res: number = 0
let n: number = t.length
let visit: boolean[] = new Array(n).fill(false)
/**
 *
 * @param {*} path 子序列在s索引组成的数组
 */
const trackback = (path: number[]): void => {
    if (path.length === n) {
        res++
        return
    }
    for (let i = 0; i < n; i++) {
        if (!visit[i]) {
            if (path.length === 0) {

            } else {

            }
        }
    }
}
trackback([])
console.log(res)

export {};

源码：ts/leetcode/115. 不同的子序列.ts

解法二 · TypeScript ​

TypeScript · O(2^n) 时间 · O(n) 空间 · 更新于 2026-09-27

双指针回溯，跳过或匹配 s[si] 累加方案

typescript
/**
 * @difficulty hard
 * @tags 回溯,字符串,子序列
 * @time O(2^n)
 * @space O(n)
 * @note 双指针回溯，跳过或匹配 s[si] 累加方案
 * @115. 不同的子序列（解法二）
 * 双指针回溯...
 */
let s: string = "rabbbit"
let t: string = "rabbit"
let res: number = 0

const backtrack = (si: number, ti: number): void => {
    if (ti === t.length) {
        res++
        return
    }
    if (si >= s.length) return
    // 跳过s[si]
    backtrack(si + 1, ti)
    // 如果匹配，则选择s[si]
    if (s[si] === t[ti]) {
        backtrack(si + 1, ti + 1)
    }
}

backtrack(0, 0)
console.log(res) // 3

// 初始状态: si=0, ti=0, res=0

// 第1步: backtrack(0,0)
// ├─ 跳过s[0]='r': backtrack(1,0)
// │  ├─ 跳过s[1]='a': backtrack(2,0)
// │  │  ├─ 跳过s[2]='b': backtrack(3,0)
// │  │  │  ├─ 跳过s[3]='b': backtrack(4,0)
// │  │  │  │  ├─ 跳过s[4]='b': backtrack(5,0)
// │  │  │  │  │  ├─ 跳过s[5]='i': backtrack(6,0)
// │  │  │  │  │  │  ├─ 跳过s[6]='t': backtrack(7,0) → si>=s.length, 返回
// │  │  │  │  │  │  └─ 匹配? s[6]='t' === t[0]='r'? No
// │  │  │  │  │  └─ 匹配? s[5]='i' === t[0]='r'? No
// │  │  │  │  └─ 匹配? s[4]='b' === t[0]='r'? No
// │  │  │  └─ 匹配? s[3]='b' === t[0]='r'? No
// │  │  └─ 匹配? s[2]='b' === t[0]='r'? No
// │  └─ 匹配? s[1]='a' === t[0]='r'? No
// └─ 匹配? s[0]='r' === t[0]='r'? Yes!
//    → backtrack(1,1)

// 第2步: backtrack(1,1)  [已匹配到t[0]='r']
// ├─ 跳过s[1]='a': backtrack(2,1)
// │  ├─ 跳过s[2]='b': backtrack(3,1)
// │  │  ├─ 跳过s[3]='b': backtrack(4,1)
// │  │  │  ├─ 跳过s[4]='b': backtrack(5,1)
// │  │  │  │  ├─ 跳过s[5]='i': backtrack(6,1)
// │  │  │  │  │  ├─ 跳过s[6]='t': backtrack(7,1) → 返回
// │  │  │  │  │  └─ 匹配? s[6]='t' === t[1]='a'? No
// │  │  │  │  └─ 匹配? s[5]='i' === t[1]='a'? No
// │  │  │  └─ 匹配? s[4]='b' === t[1]='a'? No
// │  │  └─ 匹配? s[3]='b' === t[1]='a'? No
// │  └─ 匹配? s[2]='b' === t[1]='a'? No
// └─ 匹配? s[1]='a' === t[1]='a'? Yes!
//    → backtrack(2,2)

// ...以此类推，最终找到3条路径:
// 1. s[0]r + s[1]a + s[2]b + s[3]b + s[5]i + s[6]t
// 2. s[0]r + s[1]a + s[2]b + s[4]b + s[5]i + s[6]t
// 3. s[0]r + s[1]a + s[3]b + s[4]b + s[5]i + s[6]t

export {};

源码：ts/leetcode/115. 不同的子序列（解法二）.ts

解法三 · TypeScript ​

TypeScript · O(n*m) 时间 · O(m) 空间 · 更新于 2026-09-27

一维 dp 倒序更新，s[i]==t[j] 时累加

typescript
/**
 * @difficulty hard
 * @tags dp,字符串,子序列
 * @time O(n*m)
 * @space O(m)
 * @note 一维 dp 倒序更新，s[i]==t[j] 时累加
 * @115. 不同的子序列（解法三）
 * dp解法 - 困难
 */
let s: string = "rabbbit"
let t: string = "rabbit"

let n: number = t.length
//dp表示
let dp: number[] = new Array(n + 1).fill(0)
dp[0] = 1
for (let i = 0; i < s.length; i++) {
    for (let j = n - 1; j >= 0; j--) {
        if (s[i] === t[j]) {
            dp[j + 1] += dp[j]
        }
    }
}
console.log(dp)
console.log(dp[n])

export {};

源码：ts/leetcode/115. 不同的子序列（解法三）.ts

在 GitHub 上查看题目所在目录：lmliheng/algorithm