Programming

Leetcode-28. Find the Index of the First Occurrence in a String

By PattySung 26 June 2023
Leetcode-28. Find the Index of the First Occurrence in a 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.

Example 1:

Input: haystack = "sadbutsad", needle = "sad"
Output: 0
Explanation: "sad" occurs at index 0 and 6.
The first occurrence is at index 0, so we return 0.

Example 2:

Input: haystack = "leetcode", needle = "leeto"
Output: -1
Explanation: "leeto" did not occur in "leetcode", so we return -1.
<解題>
  1. haystack的長度比needle的長度長，故if(haystack.length<needle.length)->return -1
  2. 兩者相等->return 0
  3. 迴圈：從haystack中跑到每個字母的substring和needle一樣，return i
1.直接使用substring

public int strStr(String haystack, String needle) {
    int l1=haystack.length();
    int l2=needle.length();
    if(l1<l2)
    {
        return -1;
    }
    else if(l2==0)
    {
        return 0;
    }
    for(int i=0;i<=l1-l2;i++)
    {
        if(haystack.substring(i,i+l2).equals(needle))
        {
            return i;
        }
    }
    return -1;
}
2.如果不能使用substring

class Solution {
    public int strStr(String haystack, String needle) {
        int l1 = haystack.length();
        int l2 = needle.length();
        if (l1 < l2) {
            return -1;
        } else if (l2 == 0) {
            return 0;
        } else {
            for (int i = 0; i <= l1 - l2; i++) {
                boolean found = true; //先預設為true
                for (int j = 0; j < l2; j++) { //找接下來字母有無相同
                    if (haystack.charAt(i+j) != needle.charAt(j)){
                        found =false;
                        break;
                    }
                }
                if (found){
                    return i;
                }
            }
        }
        return -1;
    }
}