题目描述

小王很喜欢研究字符串问题，他想要知道一个字符串内，有多少种不重复的方式选出若干子串，拼接成 abcdefgh, 这里对子串不同的定义为内容不同，例如 abab 中选前两位组成的 ab 和后两位组成的 ab 是一样的，因为都是 ab

保证给定的字符串中仅包括小写字母

给定的字符串长度 <= 10000

输入： 一行字符串，表示待选的字符串 输出：一个正整数，表示多少种不同的方式

测试用例

• 输入：aabhgfdec

• 输出：4 解释：

• 第一种：a + b + c + d + e + f + g + h

• 第二种：ab + c + d + e + f + g + h

• 第三种：a + b + c + de + f + g + h

• 第四种：ab + c + de + f + g + h

代码实现

方法1：dp

var __readline = require("readline-sync");
__readline.setDefaultOptions({ prompt: "" });
var readline = __readline.prompt;

console.log("请输入str: ");
const str = readline();
function countUniqueSubstrings(str) {
  const target = "abcdefgh";
  const targetLen = target.length;
  // dp[i] 表示以 target 的前 i 个字符结尾的子串拼接方式的数量
  const dp = Array(targetLen + 1).fill(0); // 动态规划数组
  dp[0] = 1;

  for (let i = 1; i <= targetLen; i++) {
    for (let j = 0; j < i; j++) {
      const substr = target.substring(j, i);
      // 依次检查target从 j 到 i-1 的子串是否是 str 的子串
      if (str.includes(substr)) {
        dp[i] += dp[j];
      }
    }
  }
  console.log("dp: ", dp);

  return dp[targetLen];
}

console.log("结果为: ", countUniqueSubstrings(str));

方法2： 回溯

      backtracking(temp, i + 1, num + str[i].length);
      temp.pop();
    }
  }
  let count = 0;
  str.sort((a, b) => a.charCodeAt(0) - b.charCodeAt(0));
  backtracking([], 0, 0);
  return count;
}

console.log("结果为: ", findComp(str));