单词拆分

题意

判断字符串能否拆分为字典中的单词。

思路

dp[i] 表示前 i 个字符是否可拆分。枚举断点 j，若 dp[j] 且 s[j:i] 在字典中，则 dp[i] = true。找到即 break，无需继续枚举。

代码

cpp

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#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool wordBreak(string s, vector<string> &wordDict) {
        unordered_set<string> dict(wordDict.begin(), wordDict.end());
        int n = s.size();
        vector<bool> dp(n + 1, false);
        // dp[i] 表示前缀 s[0..i) 能否被字典中的单词完整拆分。
        dp[0] = true;
        for (int i = 1; i <= n; i++)
            for (int j = 0; j < i; j++)
                if (dp[j] && dict.count(s.substr(j, i - j))) {
                    dp[i] = true;
                    break;
                }
        return dp[n];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    int m;
    cin >> s >> m;
    vector<string> dict(m);
    for (auto &x : dict)
        cin >> x;
    cout << Solution().wordBreak(s, dict) << '\n';
    return 0;
}

python

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#!/usr/bin/env python3
from typing import List


class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        d = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)
        dp[0] = True
        for i in range(1, n + 1):
            for j in range(i):
                if dp[j] and s[j:i] in d:
                    dp[i] = True
                    break
        return dp[n]


def main():
    s = input().strip()
    m = int(input())
    d = [input().strip() for _ in range(m)]
    print(Solution().wordBreak(s, d))


if __name__ == "__main__":
    main()

复杂度

时间复杂度： $O(n^2)$ ，每个 i 枚举所有 j。
空间复杂度： $O(n)$ 。

总结

单词拆分是"前缀可拆分"的典型 DP：dp[i] 的含义是"前 i 个字符可拆分"，枚举断点找子串。

目录

题意

思路

代码

复杂度

总结