如何判断输入字符串是否完全由指定的子串拼接组成

开发者阿泽

2026-10-6

解法思路

你要实现的是经典的「单词拆分」类问题，确实用动态规划实现逻辑最清晰，落地步骤如下：

第一步定义状态：设dp[i]表示字符串的前i个字符（也就是下标0到i-1的子串）是否可以完全由给定的子串拼接组成
第二步设定初始状态：空字符串天然符合要求，所以dp[0] = true
第三步状态转移：遍历字符串的每个位置i（从1到字符串总长度），对每个候选子串做判断：
1. 先看当前候选子串的长度len是否小于等于i，如果更长直接跳过
2. 再判断dp[i - len]是否为true（也就是前i-len个字符已经可以合法拼接）
3. 最后判断从i-len到i的子串是否和当前候选子串完全相等
4. 以上三个条件都满足的话，就可以判定dp[i] = true，直接跳出当前候选子串的遍历即可
最终结果就是dp[字符串总长度]的值

代码实现（JavaScript）

function check(s) {
  const candidates = ['a', 'abb', 'aaaa']
  const n = s.length
  // 初始化dp数组，默认全为false
  const dp = new Array(n + 1).fill(false)
  dp[0] = true
  for (let i = 1; i <= n; i++) {
    for (const cand of candidates) {
      const len = cand.length
      if (i < len) continue
      if (dp[i - len] && s.slice(i - len, i) === cand) {
        dp[i] = true
        break
      }
    }
  }
  return dp[n]
}