LeetCode Js-28. Find the Index of the First Occurrence in a String(原Implement strStr())

    AllenLi
    LeetCode Js-String

    Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
    For the purpose of this problem, we will return 0 when needle is an empty string. 

    給予兩個字串「needle」、「haystack」，回傳「needle」在「haystack」相符的"第一個"陣列位置，如不符合則回傳-1。
當「needle」為空值時，回傳0。

    Example 1: new test

    Input: haystack = "sadbutsad", needle = "sad"
Output: 0

    Example 2: new test

    Input: haystack = "leetcode", needle = "leeto"
Output: -1

    Example 1: old test

    Input: haystack = "hello", needle = "ll"
Output: 2

    Example 2: old test

    Input: haystack = "aaaaa", needle = "bba"
Output: -1

    Example 3: old test

    Input: haystack = "a", needle = ""
Output: 0

    Solution:
    1. if「needle」是空值，回傳0
    2. if「haystack」是空值或「needle.length」比「haystack.length」大，回傳-1
    3. for迴圈跑haystack的長度，並運用.slice()帶入neeedle進行比較
    ex.類似excel的MID函式，而.substr()會取陣列起點值，.substring()會取陣列終點值。
    (A1 = ABCDEF; =MID(A1,2,1); B )
    4.正確回傳陣列起點值，錯誤回傳-1

    Code 1:

    var strStr = function(haystack, needle) {
    if (!needle) return -1
    if (!haystack || needle.length > haystack.length) return -1
    
    for (i = 0; i < haystack.length; i++) {
        let str = haystack.slice(i, i + needle.length)
        if (str === needle)  return i
    }
    return -1
};

    FlowChart:
    Example 1

    needle.length = 2 //"ll"的長度為兩個字串
step.1
haystack = "hello"
i = 0
str = haystack.length(0, 2) => "he" !== "ll"

step.2
i = 1
str = haystack.length(1, 2) => "el" !== "ll"

step.3
i = 2
str = haystack.length(1, 2) => "ll" === "ll"
return i // i = 2

    Example 2

    needle.length = 3 //"bba"的長度為一個字串
step.1
haystack = "aaaaa"
i = 0
str = haystack.length(0, 3) => "aaa" !== "bba"

step.2
i = 1
str = haystack.length(1, 3) => "aaa" !== "bba"

step.3
i = 2
str = haystack.length(2, 3) => "aaa" !== "bba"

step.4 
i = 3 
str = haystack.length(3, 3) => "aaa" !== "bba"

step.5
i = 4
str = haystack.length(4, 3) => "aaa" !== "bba"
return -1

    Example 3

    needle.length = "" //""的長度為零個字串
step.1
if (!needle) return 0

    Remark: 暴力解 => 使用indexOf可以將陣列中找到符合()的值，並回傳陣列的位置，否則回傳-1
    Code 2:

    var strStr = function(haystack, needle) {
    return haystack.indexOf(needle);
};

    Code 3:

    const strStr = (haystack, needle) => haystack.search(needle);

    // Code 4:

    var strStr = function (haystack, needle) {
  return haystack.includes(needle) ? haystack.indexOf(needle) : -1;
};

    Related Posts