javascript - 使用javascript检查字符串是否是数组中字符串的组合

Question

我需要检查一个字符串是否由数组中给定的字符串的任意组合组成示例:我们有数组 ["for","car","keys","forth"] 和一串“forthcarkeys”，结果应该是 true。如果字符串是“forthcarxykeys”，结果应该是 false因为 xy 不在数组中。数组中的单词顺序无关紧要。 不必匹配数组中的所有字符串，但测试字符串只能由数组中的任何字符串组成。如果它包含除数组中的字符串之外的任何字符串，则返回 false

我的方法:

var str = "forthcarkeys";
var arr = ["for","car","keys","forth"];
for(var i=0;i<arr.length;i++)
{
   if(str.indexOf(arr[i]) !== -1)
   {
      str.replace(arr[i],"");
   }
}

if(str !== "")
{
  console.log("yes");
} else 
{
  console.log("no");
}

但这种方法效率不高而且失败了。

Answer 1

一种可能的方法是检查每个前缀是否可以使用输入字符串表示。

这个想法是，如果我们可以很容易地计算出长度为 i 的前缀是否可以用输入字符串表示，如果我们已经有了较短前缀的信息(这可以通过检查是否任何允许的字符串都会导致更短的可表达前缀)——参见下面的代码。

var str = "forthcarkeys";
var arr = ["for","car","keys","forth"];

// isPossible[i] indicates whether we can express the 
// prefix str.substring(0, i) using strings in arr.
var isPossible = Array(str.length + 1).fill(false);

// it is always possible to construct the empty string
isPossible[0] = true;

// consider each prefix of str, from shortest to longest
for (var i = 1; i <= str.length; i++) {
  // try to reach this prefix using an allowed string s_allowed,
  // by appending s_allowed to a shorter prefix
  for (var j = 0; j < arr.length; j++) {
    // "start" is the position where the current string 
    // would need to be appended
    start = i - arr[j].length;

    if (start >= 0 && isPossible[start]) {
      if (str.substring(start, i) == arr[j]) {
        isPossible[i] = true;
        // we break the loop over j, because we already found a
        // solution to express the current prefix str.substring(0,i)
        break;
      }
    }
  }
}

for (var i = 1; i <= str.length; i++) {
  console.log(str.substring(0, i) + " - " + isPossible[i] + "\n")
}

if (isPossible[str.length]) {
  console.log("yes");
} else {
  console.log("no");
}

要进一步详细说明其工作原理，请考虑一个较小的示例:

• str = "abcd"
• arr = ["ab", "a", "cd"]

这里描述的方法测试 str 的所有前缀，按照它们长度的递增顺序:

第 0 步:空前缀——这被认为总是好的(可以用 0 字符串表示)。

---

第 1 步:前缀“a”:

我们尝试使用较短的前缀 + 一个允许的字符串来达到此前缀。为此，我们遍历允许的字符串:

• “ab”不能附加到较短的前缀以得到“a”(因为起始位置需要为 -1)。
• “a”可以附加到空前缀，这总是没问题的——因此我们得到前缀“a”没问题(可以使用允许的字符串表示)。

---

第 2 步:前缀“ab”:

我们尝试使用较短的前缀 + 一个允许的字符串来达到此前缀。为此，我们遍历允许的字符串:

• “ab”可以附加到空前缀，这总是没问题的——因此我们得到前缀“ab”没问题(可以使用允许的字符串表示)。

---

第 3 步:前缀“abc”:

我们尝试使用较短的前缀 + 一个允许的字符串来达到此前缀。为此，我们遍历允许的字符串:

• "ab"-- 要将此附加到较短的前缀并获得当前的 "abc"前缀，我们需要从位置 1 开始，但从该开始位置开始的子字符串是 "bc"，因此我们不能追加字符串“ab”以获得前缀“abc”。
• "a"-- 与上面类似，我们不能附加 "a"以获得前缀 "abc"。
• "cd"-- 与上面类似，我们不能附加 "cd"以获得前缀 "abc"。

我们用尽了所有允许的字符串，因此无法使用允许的字符串前缀“abc”表示。

---

第 4 步:前缀“abcd”(整个字符串):

我们尝试使用较短的前缀 + 一个允许的字符串来达到此前缀。为此，我们遍历允许的字符串:

• "ab"-- 要将此附加到较短的前缀并获得当前的 "abcd"前缀，我们需要从位置 2 开始，但从该开始位置开始的子字符串是 "cd"，因此我们不能附加字符串“ab”以获得前缀“abcd”。
• "a"-- 与上面类似，我们不能附加 "a"以获得前缀 "abcd"。
• “cd”——我们可以将这个允许的字符串附加到“ab”前缀。在上一步中，我们发现“ab”前缀没问题(可以用给定的字符串表示)，因此从那里附加“cd”没问题。

因此，我们得到前缀“abcd”(对应整个字符串)可以用输入字符串表示。