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:然后我们尝试使用include Javascript方法查找字典中的单词是否包含存储在firstSubString中的值。
步骤5:如果字典包含第一个子字符串,我们将第一个单词之后开始的第二个子字符串存储在secondSubString变量中。
步骤6:如果secondSubString变量的长度为0,则它只返回已在字典中找到的第一个子字符串分段字符串,并返回true作为结果输出。
步骤7:如果secondSubString已经使用include方法存在于单词字典中,则结果输出也返回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,因此复杂度由此确定。
我们可以使用备忘录法将时间复杂度提高到O(n^2),其中备忘录法将占用一些内存来存储已经为某些字母执行的步骤,而不是重复它们。
使用上述算法,我们可能会多次计算相同的子字符串或字符,每次迭代都向前移动并朝着字符串数组的长度移动,即使完成的子字符串可能两次或多次不存在于字典中,这也会增加递归子调用,而备忘录法可以减少算法的这一部分。
备忘录法是指我们将记住已经解决的子字符串。
算法 - 使用备忘录法
步骤1:声明一个名为segmentString的主函数,该函数以字符串数组和单词字典作为输入。
步骤2:从中返回一个辅助递归函数,该函数接受字符串数组、单词字典、字符串的起始位置和一个用于备忘录法的空数组。
步骤3:在名为recursiveWordFind的辅助函数内部,我们使用基本情况:如果字符串数组等于长度,则返回true;如果备忘录数组的起始位置不等于undefined,则返回起始索引的内存。
步骤4:使用起始和结束位置标志遍历字符串数组,以便第一个单词或第一个子字符串是具有起始位置的数组,而第二个子字符串从start +1的索引开始用于结束标志。
步骤5:提取起始和结束位置之间的子字符串,并将其存储在inputSubString变量中。
步骤6:一旦你在字典中找到了起始和结束位置之间的特定子字符串,并为主字符串数组中剩余的字符再次重复递归函数,则返回所有字符串字符的内存引用,以便不会为已经遍历的子字符串重复相同的递归函数,从而节省函数的效率。
主代码 - 使用备忘录法
示例
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));
输出
true
时间和空间复杂度
备忘录法使用内存引用或内存容器来保存循环和递归函数的循环,因此时间复杂度从指数级最坏时间降低到二次时间复杂度,即O(n^2)。
结论
这就是我们如何在逻辑上和编码上下文中解决上述问题陈述的方法,在这种情况下,这类问题陈述可以在时间、优化和最佳效率方面有效增长。