[LeetCode] 28. Implement strStr() (C#)

LeetCode - Problems - Algorithms - 28. Implement strStr()

Problem Description

28. Implement strStr() - Description

28. Implement strStr() - Examples and Contstraints

My Solution (C#)

변수 이름에서 알 수 있듯이, 주어진 string 건초더미에서 string 바늘이 있는지 찾는 문제이다.

C#의 IndexOf (C의 경우는 StrStr)를 구현하는 문제다.

Description을 끝까지 안읽어서 (끝까지 읽읍시다...) IndexOf를 사용해서 풀었다. (??)

// Implementing IndexOf by using IndexOf (???)
public class Solution {
    public int StrStr(string haystack, string needle) {
        if (string.IsNullOrEmpty(needle))
            return 0;
        else if (string.IsNullOrEmpty(haystack))
            return -1;
        if (!haystack.Contains(needle))
            return -1;
        return haystack.IndexOf(needle);
    }
}

LeetCode에서는 받아주지만 실제 이런 문제가 나왔을때 이렇게 풀면 오답이다!

//Implementing IndexOf in right way
public class Solution {
    public int StrStr(string haystack, string needle) {
        if (string.IsNullOrEmpty(needle))
            return 0;
        else if (string.IsNullOrEmpty(haystack))
            return -1;

        string temp;
        int index = 0;
        while (index <= haystack.Length - needle.Length)
        {
            temp = haystack.Substring(index, needle.Length);
            if (temp == needle)
                return index;
            index++;
        }
        return -1;
    }
}

• needle이 null 혹은 "" 인지 확인하기. (return 0 when the needle is en empty string).
  • 아니라면 haystack이 null 혹은 ""인지 확인하기. (needle cannot be part of haystack)
• needle의 길이만큼 저장할 임시 변수를 위해 string temp를 선언해주었고, temp에 저장할 값의 haystack 시작 지점을 저장하기 위한 int index를 0으로 선언했다.
• 반복문은 index가 haystack의 길이에서 needle의 길이를 뺀 것보다 적을 때. (to prevent 'array index is out of range' error)
  • Substring을 이용해 index값부터 needle의 길이만큼의 string 값을 temp에 저장한다
  • temp와 needle이 같다면 나머지 값을 확인할 필요가 없으니 바로 index값을 return한다. (needle이 시작되는 위치)
  • 아니라면 index 값을 증가시켜서 반복하도록 한다.
• 반복문이 끝났음에도 StrStr method가 종료되지 않았다는 것은 haystack에 needle이 없다는 의미이므로 -1을 return한다. (needle is not part of haystack)

Compare two solutions' runtime

중간에 Wrong Answer를 기준으로:

• 위는 Substring을 이용해 올바르게 IndexOf를 구현한 솔루션을 제출했을 때의 결과
• 아래는 IndexOf를 이용해 IndexOf를 구현한 잘못된 솔루션 제출 결과이다.

Leetcode runtime은 상당히 뒤죽박죽이기 때문에 (같은 솔루션을 제출해도 다른 결과가 나올 때가 많다.) 여러번 제출하는 편인데, 그 평균 값이 현저히 차이가 나는 것을 확인할 수 있다.

 

[LeetCode] 28. Implement strStr() (C#)