leetcode - 實(shí)現(xiàn)strStr()

題意

實(shí)現(xiàn)strStr()函數(shù)。

給你兩個(gè)字符串haystack和needle ，請(qǐng)你在haystack字符串中找出needle字符串出現(xiàn)的第一個(gè)位置（下標(biāo)從0開(kāi)始）。如果不存在，則返回-1。

當(dāng)needle是空字符串時(shí)，我們應(yīng)當(dāng)返回什么值呢？這是一個(gè)在面試中很好的問(wèn)題。

對(duì)于本題而言，當(dāng)needle是空字符串時(shí)我們應(yīng)當(dāng)返回 0。這與 C 語(yǔ)言的strstr()以及 Java 的indexOf()定義相符。

示例

示例 1：

輸入：haystack = "hello", needle = "ll"
輸出：2

示例 2：

輸入：haystack = "aaaaa", needle = "bba"
輸出：-1

示例 3：

輸入：haystack = "", needle = ""
輸出：0

提示

• 0 <= haystack.length, needle.length <= 5 \* 104

• haystack 和 needle 僅由小寫英文字符組成

出處

鏈接：https://leetcode-cn.com/problems/implement-strstr/

思路

這里對(duì)題目給出的題意我們先考慮特殊情況，比如最后提到的空字符串返回什么問(wèn)題， 然后可以根據(jù)兩個(gè)參數(shù)的長(zhǎng)度進(jìn)行分類討論，之后的話做法是把haystack所有可以出現(xiàn)的位置存到一個(gè)數(shù)組里面，然后我們?nèi)ケ闅v它，在里面遍歷needle，如果每個(gè)都相等的話，那么我們就把存進(jìn)數(shù)組的左指針?lè)祷?/p>

代碼

const strStr = function (haystack, needle) {
  if (needle === '') {
    return 0;
  }
  const haystack_len = haystack.length;
  const needle_len = needle.length;
  if (needle_len > haystack_len) {
    return -1;
  } else if (needle_len === haystack_len) {
    return haystack === needle ? 0 : -1;
  }
  const target = needle[0];
  const position = [];
  for (const index in haystack) {
    if (haystack[index] === target) {
      position.push(+index);
    }
  }
  for (const left of position) {
    let right = left;
    for (let i = 0; i < needle_len; i++) {
      if (haystack[right] === needle[i]) {
        if (i === needle_len - 1) {
          return left;
        }
        right++;
      } else {
        break;
      }
    }
  }
  return -1;
};

export default strStr;

測(cè)試

import strStr from '../../code/leetcode/28';

describe('test function strStr:', () => {
  test('test case str="mississippi", needle="mississippii", target = -1', () => {
    const data = strStr('mississippi', 'mississippii');
    expect(data).toEqual(-1);
  });

  test('test case str="mississippi", needle="mississippii", target = -1', () => {
    const data = strStr('mississippi', 'issi');
    expect(data).toEqual(1);
  });

  test('test case str="a", needle="a", target = 0', () => {
    const data = strStr('a', 'a');
    expect(data).toEqual(0);
  });

  test('test case str="abc", needle="c", target = 2', () => {
    const data = strStr('abc', 'c');
    expect(data).toEqual(2);
  });

  test('test case str="hello", needle="ll", target = 2', () => {
    const data = strStr('hello', 'll');
    expect(data).toEqual(2);
  });

  test('test case str="aaaaa", needle="bba", target = -1', () => {
    const data = strStr('aaaaa', 'bba');
    expect(data).toEqual(-1);
  });

  test('test case str="", needle="", target = 0', () => {
    const data = strStr('', '');
    expect(data).toEqual(0);
  });
});

說(shuō)明

本文首發(fā)于 GitHub 倉(cāng)庫(kù)https://github.com/ataola/coding，線上閱讀地址：https://zhengjiangtao.cn/coding/，轉(zhuǎn)載請(qǐng)注明出處，謝謝！