JavaScript 能够分割字符串吗

问题陈述要求检查由用户输入的字符串是否可以分割。

什么是分割字符串

字符串中的分割是指将整个字符串文本中的单词分解为输入。这些单词会被拆分成字典中的单词。问题陈述更加复杂，并深入研究了一些完整的词典和字符串文本，并且我们必须检查分割或拆分的字符串是否与所提到的词典中的单词相匹配。

以下给出了问题陈述的可视化输出：

Given dictionary of words :  “apple , peer , pie , please , have “

Input String : “haveapplepie”

Output :  true

如果输入的字符串可以根据用户提供的词典中的单词分割和拆分，则结果输出为true，否则返回false。

步骤

这里提到的算法是使用循环和JavaScript的include方法的一种暴力方法，用于查找和检查输入的字符串是否可以分割。

步骤1 ：声明一个名为checkSegmentation的函数，该函数以字符串数组作为输入，并使用一组词汇数组作为字典单词，通过使用这些单词，可以找出特定字符串是否可以分割。

步骤2 ：从for循环开始，可以遍历字符串的每个字符，直到stringArray.length。

步骤3 ：当i的值为0时，我们使用substr方法将该值存储为第一个单词，并将其存储在firstSubString变量中。

步骤4 ：然后，尝试查找字典中是否包含以firstSubString存储的值，使用include JavaScript方法。

步骤5 ：如果字典包含第一个子字符串，则将在第一个单词之后开始的第二个子字符串存储在secondSubString变量中。

步骤6 ：如果secondSubString变量的长度为0，则只返回已在字典中找到的第一个子字符串分割字符串，并以true作为结果输出。

步骤7 ：如果使用include方法在字典中已经存在secondSubString，则结果输出也会返回true，表示字符串可以分割。

步骤8 ：如果6或7步骤中的任何一步未发生，则主函数checkSegmentation成为对secondSubString执行所有操作和算法步骤的递归函数，这些操作和算法步骤与字典中的单词有关。

示例

function checkSegmentation(stringArray, dictionaryArray) {

   for (let i = 1; i < stringArray.length + 1; i++) 
     {

     let firstSubString = stringArray.substr(0, i);

      if (dictionaryArray.includes(firstSubString)) {

        let secondSubString = stringArray.substr(i);

     if (secondSubString.length === 0) {

         return true;
      }

     if (dictionaryArray.includes(secondSubString)) {

         return true;
      }

     if (checkSegmentation(secondSubString, dictionaryArray)) {

        return true;

      }

     }

   }

return false;

};

const dictionaryArray =  "apple , peer , pie , please , have ";

const stringArray =  "haveapple";

console.log(checkSegmentation(stringArray,dictionaryArray));

输出

true

以下的代码是在看到问题描述后思考到的最简单的方法，接下来我们可以将其优化为更优质的空间和时间，使其更高效和高质量。

在上面的代码中，我们声明了一个名为checkSegmentation的函数，该函数使用字符串数组和字典值来检查字符串的分段。

在这里，我们通过遍历字符串的每个元素来构造子词，希望在每次迭代中使用javascript的include方法来查找字典中的子词。

时间和空间复杂度

由于该算法是递归算法，并且每次在找不到包含第二个子字符串的字典之前都要进行递归调用，所以最坏情况下的时间复杂度是指数级的O(2^n)，因为递归函数导致形成一个高度为2^n的树状结构的子递归分支，因此复杂度是由此保证的。

我们可以使用Memoization将时间复杂度提高到O(n^2)，其中Memoization将花费一些内存来存储已经针对某些字母执行的步骤，而不是再次重复执行它们。

通过上述算法，即使我们迭代地向前移动并朝着字符串数组的长度前进，即使已完成的子字符串可能出现两次或更多次也不存在于字典中，我们可能会多次以不同的方式计算相同的子字符串或字符，这增加了递归子调用的次数，而Memoization可以减少该算法的这一部分。

Memoization是一种记住已经解决的子字符串的方法。

方法- 使用Memoization

步骤1： 声明一个名为segmentString的主函数，该函数接受一个字符串数组和一个单词字典作为输入。

步骤2： 在该函数中返回一个帮助函数和递归函数，该函数接受字符串数组、单词字典、字符串的起始位置和用于Memoization的空数组作为输入。

步骤3： 在名为recursiveWordFind的帮助函数内部使用基本情况，即如果字符串数组等于长度，则返回true，并且如果memo数组的起始位置不等于undefined，则返回开始索引的记忆。

步骤4： 遍历字符串数组，使用起始位置和结束位置标志，其中第一个单词或第一个子字符串是以起始位置为数组的，第二个子字符串从起始位置+1开始索引。

步骤5： 提取起始位置和结束位置之间的子字符串，并将其存储在inputSubString变量中。

步骤6： 一旦在起始位置和结束位置之间找到特定的子字符串，并且再次对主字符串数组中剩余的字符执行递归函数，请返回所有字符串字符的记忆引用，以便不重复执行已经遍历过的子字符串的相同递归函数，从而节省函数的功耗。

代码 – 使用Memoization

示例

function segmentString(  stringArray , dictionaryArray )
{
   return recursiveWordFind( stringArray , dictionaryArray , 0  , []);
}



function recursiveWordFind( stringArray  ,dictionaryArray , start , memo )
{ 
   if(start===stringArray.length) return true ;

   if(memo[start]!==undefined) return memo[start];

   for(let end = start +1 ; end <= stringArray.length ; end++)
   {

     let inputSubString = stringArray.substring(start,end);

     if(dictionaryArray.includes(inputSubString) && recursiveWordFind(stringArray , dictionaryArray , end , memo))

     {

      return memo[start]=true;

     }

   }

   return memo[start]=false;
}

const dictionaryArray =  ["apple", "pen"];

const stringArray =  "applepenapple";

console.log(segmentString(stringArray,dictionaryArray));