LeetCode单词拆分问题：构建矩阵后如何继续求解？

首先修正你当前矩阵构建代码的逻辑问题：你现在的写法会把A[i]行中从i到j-1的所有位置设为True，这不符合矩阵的定义逻辑。正确的矩阵A应该是**A[i][j] = True 当且仅当子串 word[i:j+1]（即索引i到j的闭区间子串）存在于字典中**。修正后的矩阵构建代码如下：

word = "catsandog"
wordDict = set(["cats","dog","sand","and","cat"])

n = len(word)

# A[i][j] 表示子串 word[i..j]（闭区间）是否在字典中
A = [[False] * n for _ in range(n)]

for length in range(1, n+1):  # 遍历所有可能的子串长度
    for i in range(n - length + 1):
        j = i + length - 1
        substr = word[i:j+1]
        if substr in wordDict:
            A[i][j] = True

接下来，我们可以结合这个矩阵用动态规划推导最终结果，步骤如下：

• 定义dp数组：dp[k]表示前k个字符（即word[0..k-1]）是否可以拆分为字典中的单词组合。
• 初始状态：dp[0] = True，因为空字符串默认可以被拆分。
• 状态转移：对于每个k（从1到n），遍历所有m（从0到k-1），如果dp[m]为True，且A[m][k-1]为True（说明word[m..k-1]是字典中的有效单词），那么dp[k] = True。
• 最终结果：dp[n]就是整个字符串是否可以被拆分的答案。

对应的实现代码：

dp = [False] * (n + 1)
dp[0] = True

for k in range(1, n+1):
    for m in range(k):
        if dp[m] and A[m][k-1]:
            dp[k] = True
            break  # 找到一种拆分方式即可，无需继续遍历

print(dp[n])  # 示例输入输出为False

逻辑解释 #

以你的示例输入"catsandog"为例：

• 当k=3时，m=0，dp[0]为True，且A[0][2]（对应子串"cat"）为True，所以dp[3] = True。
• 当k=4时，m=0，A[0][3]（"cats"）为True，所以dp[4] = True。
• 当k=7时，m=3，A[3][6]（"sand"）为True且dp[3]为True，或者m=4时A[4][6]（"and"）为True且dp[4]为True，都能得到dp[7] = True。
• 但当k=9（整个字符串长度）时，遍历所有m从0到8，找不到任何一个m满足dp[m]为True且A[m][8]为True，所以dp[9]保持False，也就是最终结果。

内容的提问来源于stack exchange，提问作者parzival123