在Javascript中查找不包含/ indexOf / Regex的字符串中的子字符串

问题描述 投票:2回答:5

我想知道子串是否在字符串中,而不使用Qazxswpoi,includes(任何类似的)或正则表达式的Javascript内置方法。基本上只是想学习一种算法方法。

这就是我到目前为止所拥有的

indexOf

我无法理解如何构建算法。一旦找到匹配的第一个字符,我就会转到下一个字符,如果匹配则继续到字符串的下一个索引?那么我是否需要一个与我目前正在进行的循环分开的递归函数?我正在努力改进算法思维。谢谢。

javascript algorithm
5个回答
2
投票

这是algorythm isSubstring的优化示例。它只迭代所需的最小字符数。

例如,如果字符串长度为20个字符且子字符串长度仅为5个字符,那么当我们到达字符串的第16个位置时,我们可以假设字符串中不存在子字符串(16 + 5 = 21> 20 )

function isSubstring(string, substring){
    substringIndex = 0;

    // loop through string
    for(let i = 0; i< string.length; i++){

       //check the current substring index if it matches 
       if(string[i] === substring[substringIndex]){
           substringIndex++
          //continue searching... Would i then have to call another function recursively?
       }

    }

}

2
投票

许多方法都是可能的。这是一个:创建一个更简单的函数,它将检查function isSubstring(str, sub){ if(sub.length > str.length) return false; for(let i = 0; i < str.length - sub.length + 1; i++){ if(str[i] !== sub[0]) continue; let exists = true; for(let j = 1; j < sub.length && exists; j++){ if(str[i+j] === sub[j]) continue; exists = false; } if(exists) return true; } return false; } //expected true console.log(isSubstring("hello world", "hello")); console.log(isSubstring("hello world", "world")); console.log(isSubstring("hello world", "d")); console.log(isSubstring("hello world", "o w")); console.log(isSubstring("hello world", "rl")); console.log(isSubstring("hello world", "")); //expected false console.log(isSubstring("hello world", "hello world 1")); console.log(isSubstring("hello world", "helloo"));字符串是否在具体指定位置,让我们在first字符串中将其命名为start。这很简单:你比较secondfirst[i]所有second[start+i]在0到i - 1的长度范围内。

然后第二步是对从0到第二个字符串长度的所有起始位置重复此函数,同时检查边界(在字符串结束后无法读取)。

稍后,当第一个版本可用时,您也可以进行一些优化。 :-)


1
投票

在大海捞针的first上的每次迭代中,使用length从该索引中提取字符(索引加上针的长度)。如果切片的字符串与针匹配,则返回true:

slice

1
投票

由于您表达了对递归方法的兴趣,因此需要考虑这一点。点击黄色降价部分可以看到剧透。

function isSubstring(string, substring) {
  for (let i = 0; i < string.length; i++) {
    const sliced = string.slice(i, i + substring.length);
    if (sliced === substring) {
      return true;
    }
  }
  return false;
}
console.log(isSubstring('foobar', 'oob'));
console.log(isSubstring('foobar', 'baz'));

function f(str, sub, i=0, j=0){ if (j && j == sub.length)

return true;

if (i == str.length)

return false;

if (str[i] == sub[j]) return f(str, sub,

i+1, j+1);

return f(str, sub,

i+1, 0);

0
投票
}

没有包含,没有.indexOf,没有RegExp。只是字符串。

© www.soinside.com 2019 - 2024. All rights reserved.