在字符串中查找子字符串

Question

我正在尝试使用 O(N) 复杂度在字符串中查找子字符串。以下是我写的代码。它 returns 未定义，我不知道为什么。请让我知道我的代码出了什么问题。

let omg = "omg";
let omgi = "omjiklmonomgib";

function stringSearch(smallString, bigString) {

  let left = 0;
  let right = left+(smallString.length - 1);

  while (left > right) {
    if (smallString[left] === bigString[left]) {
      if (smallString[right] === bigString[right]) {
        left++;
        right--;
        if (left === right) {
          if (smallString[right] === bigString[left]) {
            return true;
          } else if (right === left + 1) {
            if (smallString[right] === bigString[right] && smallString[left] === bigString[left]) {
              return true;
            } else {
              left = right + 1;
              right = left + (smallString.length - 1);
            }
          }
        }
      }
    }
  }
}

console.log(stringSearch(omg, omgi)); //Undefined

Answer 1

我发现了几个问题。首先，代码没有针对每个逻辑分支的 return 语句。我的意思是，对于 if, then, else 语句中的每个条件，代码应该有一个 return 语句或某种控制流语句（例如递归调用或继续），最终会导致return 声明。

第二个问题是 while 循环。按理说，right应该从函数开始就大于left（除非smallString的长度为0）因为right是smallerString的长度减 1。while 条件为 left > right，因此 while 内的任何内容都不会执行，除非 smallString 具有负长度（它没有）。

顺便说一下，如果你想检查整个 bigString，你需要遍历 bigString，而不是 smallString。如果您只检查 smallString.length 个字符，则不会检查整个 bigString。弄清楚如何编写这个函数是一个很好的练习，所以我将把它的编写留给你并且不自己提供实现。继续努力！

Answer 2

据我了解，您只是在改造 String.prototype.match。 ~~尝试检查一下，因为它可能是一种更简单的方法来完成您所说的。~~抱歉，错过了 O(N) 复杂度部分。

~~如果你真的想定制一个，我可以给你一些提示。~~
首先，你应该有一个“缓存”变量（一个用于所有，而不是left和right）和另一个变量found（它将是一个布尔值，所以将其设置为假）。 “缓存”变量将存储文本，另一个将存储您是否找到了 smallString.

基本上，您遍历每个字符并将 smallString 个字符存储在“缓存”变量中。一旦“缓存”变量的长度与 smallString、运行相同，则在其上添加 if 语句。如果它不等于 smallString，则删除“缓存”的第一个字符。循环中的下一次迭代，它将添加另一个字符。然后你和以前一样，运行一个 if 语句，如果它不相等，删除第一个字符并继续循环，直到找到它，或者字符串结束。如果找到它，请将布尔值设置为 true。

像这样：

function stringSearch(smallString, bigString, caseSensitive=true) {
    if(!caseSensitive) { // if caseSensitive is false, make everything lower case
        smallString = smallString.toLowerCase();
        bigString = bigString.toLowerCase();
    }
    
    let cache = ""; // string cache
    let found = false; // result

    for(i=0;i<bigString.length;i++) { // loop through every character in bigString
        cache+=bigString[i]; // add the current character to the cache
        if(cache.length == smallString.length) { // check if the cache's length is the same as the smallString's length
            if(cache == smallString) { // check if the cache is equal to the smallString
                found = true; // set found to true
                break; // break the loop (stop it from going on)
            } else {
                cache = cache.substring(1); // set cache to itself but remove the first character
            }
        }
    }

    return found; // return result
}


// example:

console.log("String 'hello, world' has 'hello': "+stringSearch("hello", "hello, world"));
console.log("String 'HELLO WORLD' has 'hello': "+stringSearch("hello", "HELLO WORLD"));
console.log("String 'HELLO WORLD' has 'hello' (not case sensitive): "+stringSearch("hello", "HELLO WORLD", false));
console.log("String 'hey hi hello WORLD' has 'hello': "+stringSearch("hello", "hey hi hello WORLD"));
console.log("String 'hey hi hello' has 'hello': "+stringSearch("hello", "hey hi hello"));
console.log("String 'hey lol o' has 'hello': "+stringSearch("hello", "hey lol o"));

在字符串中查找子字符串

Finding subString in String

javascript

arrays

string

algorithm

substring