JavaScript 中字符串可以分段吗
问题陈述说检查用户输入的字符串是否可以分段。
什么是分段字符串?
字符串中的分段是指将输入的整个字符串文本分解成单词。 这些单词被分解成字典中的单词。问题陈述更加确定，并且深入挖掘，给定一些完整的单词词典和字符串文本，我们必须检查字符串的分段或分解是否与提到的字典中的单词兼容且相等。
问题陈述可以通过以下输出可视化:
给定单词词典:"apple，peer，pie，please，have" 输入字符串:"haveapplepie" 输出:true
如果输入字符串可以根据用户提到的字典单词进行分段和分解，则结果输出返回 true，否则将返回 false。
算法
这里提到的算法是一种使用循环和 JavaScript 的包含方法来查找和检查输入字符串是否可以分段的强力方法。
步骤 1:声明一个名为 checkSegmentation 的函数，该函数以字符串数组作为输入，以字典数组作为一些单词集，使用该函数可以找出特定字符串是否可以分段。
步骤 2:从 for 循环开始，可以遍历字符串的每个字符，直到 stringArray.length 。
步骤 3:当 i = 0 时，我们使用 substr 方法将该值作为第一个单词存储在变量 firstSubString 中。
步骤 4:然后我们尝试使用查找单词词典是否包含存储在 firstSubString 中的值include javascript 方法。
步骤 5:如果字典包含第一个子字符串，我们将在 firstWord 之后开始的第二个子字符串存储在 secondSubString 变量中
步骤 6:如果 secondSubString 变量的长度为 0，则仅返回字典中已找到的 firstSubString 分段字符串，并返回 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 的树状结构，因此复杂性由此得到保证。
我们可以使用记忆化将时间复杂度提高到 O(n^2)，其中记忆化将占用一些内存来存储已经针对某些字母执行的步骤，而不是再次重复这些步骤。
使用上述算法，每次我们迭代转发并朝着字符串数组的长度移动时，我们可能会以不同的方式多次计算相同的子字符串或字符，即使完成的子字符串可能在字典中不存在两次或更多次，这也会增加递归子调用，而记忆化可以减少算法的这一部分。
记忆化是我们将记住已经解决的子字符串的地方。
算法 - 使用记忆化
步骤 1:声明一个名为segmentString的主函数，该函数以字符串数组和单词词典作为输入。
步骤 2:从中返回一个辅助函数和递归函数，该函数接受字符串数组、单词词典、字符串的开头、用于记忆化的空数组
步骤 3:在名为 recursiveWordFind 的辅助函数中，我们使用基本情况:如果字符串数组等于长度则返回 true ，如果备注数组起始位置不等于 undefined ，则返回起始索引的内存。
步骤 4:遍历带有起始和结束位置标志的字符串数组，使得第一个单词或第一个子字符串是具有起始位置的数组，而第二个子字符串以起始 +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)。
结论
这就是我们如何在编码的背景下逻辑地思考解决上述问题陈述，其中这种问题陈述可以在时间、优化和最佳效率方面有效地增长。
