LeetCode 솔루션

[Easy - wk2 - Q3] 28. Implement strStr()

Chloe 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.08 20:10

7,778 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

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.

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

Example 1:

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

Example 2:

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

Constraints:

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

#leetcode, #문제풀이, #easy, #amazon, #microsoft, #google, #facebook, #apple, #uber, #two pointers, #string, #string matching

익명
작성일 2022.05.11 11:27

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

익명
작성일 2022.05.11 20:43

python

Runtime: 67 ms, faster than 24.69% of Python3 online submissions for Implement strStr().
Memory Usage: 13.8 MB, less than 77.01% of Python3 online submissions for Implement strStr().

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

익명
작성일 2022.05.24 09:44

C++
Runtime: 3 ms, faster than 48.25% of C++ online submissions for Implement strStr().
Memory Usage: 6.3 MB, less than 33.29% of C++ online submissions for Implement strStr().

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size();
        int m = needle.size();
        
        for (int i = 0; i < n - m + 1; ++i) {
            int j = 0;
            while (j < m && haystack[i + j] == needle[j]) {
                ++j;
            }
            if (j == m) return i;
        }
        return -1;
    }
};