Python 中的分词

pythonserver side programmingprogramming更新于 2025/10/25 22:04:17

假设我们有一个非空字符串 s 和一个字典 wordDict。其中包含一个非空单词列表，确定何时可以将 s 分割成一个或多个字典单词的空格分隔序列。我们必须遵循一些规则 −

词典中的同一个词在分词过程中可能会被重复使用多次。
我们可以假设词典中不包含重复的单词。

假设字符串 s = “applepenapple”，而词典中的单词为 [“apple”, “pen”]，则输出将为 true，因为字符串 s 可以分词为 “apple pen apple”。

让我们看看步骤 −

定义一个 n x n 阶矩阵 DP。 n = 字符串的大小，并用 false 初始化它
对于 i，范围从 1 到 s 的长度
- 对于 j，范围从 0 到 s 的长度 – i
  - 如果子字符串 s[j 到 j + 1] 在字典中，则 dp[j, j+i - 1] := True
  - 否则
    - 对于 k，范围从 j + 1 到 j + i
      - 如果 dp[j, k - 1] 和 dp[k, j + i – 1]，则 dp[j, j + i – 1] := True
return DP[0, length of s - 1]

示例 (Python)

让我们看下面的实现，以便更好地理解 −

class Solution(object):
   def wordBreak(self, s, wordDict):
      dp = [[False for i in range(len(s))] for x in range(len(s))]
      for i in range(1,len(s)+1):
         for j in range(len(s)-i+1):
            #print(s[j:j+i])
            if s[j:j+i] in wordDict:
               dp[j][j+i-1] = True
            else:
               for k in range(j+1,j+i):
                  if dp[j][k-1] and dp[k][j+i-1]:
                     dp[j][j+i-1]= True
      return dp[0][len(s) - 1]
ob1 = Solution()
print(ob1.wordBreak("applepenapple", ["apple", "pen"]))