leetcode - 实现strStr()
前端路桥
共 4707字,需浏览 10分钟
·
2021-04-21 00:23
题意
实现strStr()
函数。
给你两个字符串haystack
和needle
,请你在haystack
字符串中找出needle
字符串出现的第一个位置(下标从0
开始)。如果不存在,则返回-1
。
当needle
是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当needle
是空字符串时我们应当返回 0
。这与 C 语言的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/
思路
这里对题目给出的题意我们先考虑特殊情况,比如最后提到的空字符串返回什么问题, 然后可以根据两个参数的长度进行分类讨论,之后的话做法是把haystack
所有可以出现的位置存到一个数组里面,然后我们去遍历它,在里面遍历needle
,如果每个都相等的话,那么我们就把存进数组的左指针返回
代码
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;
测试
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);
});
});
说明
本文首发于 GitHub 仓库https://github.com/ataola/coding
,线上阅读地址:https://zhengjiangtao.cn/coding/
,转载请注明出处,谢谢!
评论