Find the Index of the First Occurrence in a String[E,Two Pointers,String,String Matching]

https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string/description/

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 <= 104
• haystack and needle consist of only lowercase English characters.

1. Python

class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        return haystack.find(needle)

String의 method 한 방으로 끝..

Easy 난이도는 역시 넘 easy한가..

 

2. C

int strStr(char* haystack, char* needle) {
    if(strlen(haystack) < strlen(needle)) return -1;
    
    char temp[strlen(needle)+1];

    for(int i = 0; i<strlen(haystack);i++){
        strncpy(temp,haystack+i,strlen(needle));
        temp[strlen(needle)] = '\0';
        if(strcmp(temp,needle)==0) return i;
    }
    return -1;
}

C로는 주접을 떨었다.

 

대표적으로, 1) strncpy(x,y+i,n) -> char x[ ] 에다가 char y[ ]를 +i 지점부터 n개 복사해 넣는다는 것

단, 얘는 마지막에 null까지 추가해주진 않아서 \0을 마지막에 넣어줘야 한다.

 

그리고 C에선 String간 비교가 strcmp(x,y)로 나타내고 x,y가 같으면 0, 아니면 딴 놈을 return한다.

 

느낀점은, C에선 String 가지고 뭘 하려하면 걍 복잡하다.

 

이렇게 array 에서 Character 하나씩 단타로 빼서 비교하는 게 신상에 좋다.

int strStr(char* haystack, char* needle) {
    int h = strlen(haystack);
    int n = strlen(needle);

    if(n==0) return 0;
    if(h<n) return -1;

    for(int i = 0 ; i <= h-n ; i++){
        int j = 0;
        while(j < n && needle[j] == haystack[i+j]){
            j++;
        }
        if(j==n) return i;
    }
    return -1;
}

 

3. C++

 

class Solution {
public:
    int strStr(string haystack, string needle) {
        auto n = haystack.find(needle);

        if(n==std::string::npos) return -1;
        else return n;


    }
};

 

이것도 뭐.. method 빨로 이겼다.

string1.find(string2) 를 하면, string1에 2가 포함되어 있을 때, 그 첫 index값을 반환하며 포함 x 이면 겁나 큰 값(std::string::npos)을 반환한다. 요놈은 #include <iomanip> 선언이 필요허다.

 

class Solution {
public:
    int strStr(string haystack, string needle) {
        int h = haystack.length();
        int n = needle.length();
        
        if(h<n) return -1;
        if(n==0) return 0;

        for(int i=0;i<h;i++){
            if(haystack.substr(i,n)==needle) return i;
        }
        return -1;
    }
};

 

이렇게 substr을 이용해도 된다.

 

str1.substr(i,n) 이건 str1의 i번째 index에서 n개 추출한 놈이다.

str1.substr(i) 이렇게만 하면, str1에서 i번째까지 놈을 공백화 시킨다.