Question

Formatted question description: https://leetcode.ca/all/28.html

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.

Constraints:

1 <= haystack.length, needle.length <= 10⁴
haystack and needle consist of only lowercase English characters.

Algorithm

To solve this problem, we need to make the following judgments:

If the substring is empty, return 0
If the length of the substring is greater than the length of the parent string, return -1.

Next, we will traverse the parent string. However, we don’t need to traverse the entire parent string. We can stop traversing when there are only len(parent_str) - len(substring) + 1 characters left. This can improve computational efficiency.

For each character in the parent string, we will traverse the substring again and compare the corresponding characters. If there is an unequal position in the corresponding position, we break out of the loop. If the substring is found, we return the starting position.

Code

public class Implement_strStr {

	public static void main(String[] args) {
		String a = "abc";
		String b = "abc";

		System.out.println(a == b);
	}


	public class Solution {
	    // @para: h for haystack, n for needle
	    public int strStr(String h, String n) {
	        if(h == null || n == null || h.length() < n.length()) {
	            return -1;
	        }

	        int window = n.length();
	        for(int i = 0; i + window - 1 < h.length(); i++) {

	            if(h.substring(i, i + window).startsWith(n)) {
	                return i;
	            }
	        }

	        return -1;
	    }
	}

	public class Solution_brute_force {
	    // @para: h for haystack, n for needle
	    public int strStr(String h, String n) {
	        if(h == null || n == null || h.length() < n.length()) {
	            return -1;
	        }

	        for(int i = 0; i < h.length(); i++) {
	            if(h.substring(i).startsWith(n)) {
	                return i;
	            }
	        }

	        return -1;
	    }
	}

	// ;p
	class Solution_ha {
		public int strStr(String haystack, String needle) {
			return haystack.indexOf(needle);
		}
	}

}


############

class Solution {
    public int strStr(String haystack, String needle) {
        if ("".equals(needle)) {
            return 0;
        }

        int len1 = haystack.length();
        int len2 = needle.length();
        int p = 0;
        int q = 0;
        while (p < len1) {
            if (haystack.charAt(p) == needle.charAt(q)) {
                if (len2 == 1) {
                    return p;
                }
                ++p;
                ++q;
            } else {
                p -= q - 1;
                q = 0;
            }

            if (q == len2) {
                return p - q;
            }
        }
        return -1;
    }
}

// OJ: https://leetcode.com/problems/implement-strstr/
// Time: O(MN)
// Space: O(1)
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.size() > haystack.size()) return -1;
        for (int i = 0; i <= haystack.size() - needle.size(); ++i) {
            int j = 0;
            for (; j < needle.size() && haystack[i + j] == needle[j]; ++j);
            if (j == needle.size()) return i;
        }
        return -1;
    }
};

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        n, m = len(haystack), len(needle)
        for i in range(n - m + 1):
            if haystack[i : i + m] == needle:
                return i
        return -1

############

class Solution(object):
  def strStr(self, haystack, needle):
    """
    :type haystack: str
    :type needle: str
    :rtype: int
    """
    if len(haystack) == len(needle):
      if haystack == needle:
        return 0
      else:
        return -1

    for i in range(0, len(haystack)):
      k = i
      j = 0
      while j < len(needle) and k < len(haystack) and haystack[k] == needle[j]:
        j += 1
        k += 1
      if j == len(needle):
        return i
    return -1 if needle else 0

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
	multi := 1
	for i := 0; i < m; i++ {
		target = (target*256%mod + int(needle[i])) % mod
	}
	for i := 1; i < m; i++ {
		multi = multi * 256 % mod
	}

	for ; right < n; right++ {
		sha = (sha*256%mod + int(haystack[right])) % mod
		if right-left+1 < m {
			continue
		}
		// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
		// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
		if sha == target && haystack[left:right+1] == needle {
			return left
		}
		// 未匹配成功，left 右移一位
		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
		left++
	}
	return -1
}

function strStr(haystack: string, needle: string): number {
    const m = haystack.length;
    const n = needle.length;
    for (let i = 0; i <= m - n; i++) {
        let isEqual = true;
        for (let j = 0; j < n; j++) {
            if (haystack[i + j] !== needle[j]) {
                isEqual = false;
                break;
            }
        }
        if (isEqual) {
            return i;
        }
    }
    return -1;
}

/**
 * @param {string} haystack
 * @param {string} needle
 * @return {number}
 */
var strStr = function (haystack, needle) {
    const slen = haystack.length;
    const plen = needle.length;
    if (slen == plen) {
        return haystack == needle ? 0 : -1;
    }
    for (let i = 0; i <= slen - plen; i++) {
        let j;
        for (j = 0; j < plen; j++) {
            if (haystack[i + j] != needle[j]) {
                break;
            }
        }
        if (j == plen) return i;
    }
    return -1;
};

class Solution {
    /**
     * @param String $haystack
     * @param String $needle
     * @return Integer
     */
    function strStr($haystack, $needle) {
        $strNew = str_replace($needle, "+", $haystack);
        $cnt = substr_count($strNew, "+");
        if ($cnt > 0) {
            for ($i = 0; $i < strlen($strNew); $i++) {
                if ($strNew[$i] == "+") {
                    return $i;
                }
            }
        } else {
            return -1;
        }
    }
}

public class Solution {
    public int StrStr(string haystack, string needle) {
        for (var i = 0; i < haystack.Length - needle.Length + 1; ++i)
        {
            var j = 0;
            for (; j < needle.Length; ++j)
            {
                if (haystack[i + j] != needle[j]) break;
            }
            if (j == needle.Length) return i;
        }
        return -1;
    }
}

impl Solution {
    pub fn str_str(haystack: String, needle: String) -> i32 {
        let haystack = haystack.as_bytes();
        let needle = needle.as_bytes();
        let m = haystack.len();
        let n = needle.len();
        let mut next = vec![0; n];
        let mut j = 0;
        for i in 1..n {
            while j > 0 && needle[i] != needle[j] {
                j = next[j - 1];
            }
            if needle[i] == needle[j] {
                j += 1;
            }
            next[i] = j;
        }
        j = 0;
        for i in 0..m {
            while j > 0 && haystack[i] != needle[j] {
                j = next[j - 1];
            }
            if haystack[i] == needle[j] {
                j += 1;
            }
            if j == n {
                return (i - n + 1) as i32;
            }
        }
        -1
    }
}

28 - Implement strStr()

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions