越而胜己 / Beyond awesome

Link to problem: https://leetcode.com/problems/k-closest-points-to-origin/

We solve this type of problems with dynamic programming. Let dp[i] be the boolean whether s[0..i-1] can be broken into valid words in wordList, then we have dp[i] = any(dp[j] and (s[j..i-1] in wordList)) for 0 <= j <= i, i.e. whether we can find some index j that is less than or equal to i such that s[0..j-1] can be split into words and s[j..i-1] is also a valid word. Specially, we assign dp[0] = true, as we do not need to worry about an empty string not being in wordList.

The 1D DP algorithm uses $\O(n)$ space. Since we need to traverse the previous part of the array for every index, the time complexity is $\O(n^2)$.

我们可以用动态规划来解决这一类问题。令 dp[i] 表示 s[0..i-1] 是否可以分割为 wordList 中的单词,那么有 dp[i] = any(dp[j] and (s[j..i-1] in wordList)) for 0 <= j <= i,即是否能找到某个不超过 i 的下标 j 使得 s[0..j-1] 可以分割为单词且 s[j..i-1] 也是有效的单词。特别地,我们令 dp[0] = true,因为我们不需要担心空的字符串不在 wordList 中。

使用一维 DP 的空间复杂度为 len(dp) 即 $\O(n)$,而时间复杂度由于对每个元素都需要遍历之前部分的数组,为 $\O(n^2)$。

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