문자열 안에서 문자열 검색하기

오늘의 풀어볼 문제는 "문자열 안에서 문자열 검색하기" 이다.

(link : leetcode.com/problems/implement-strstr/ )

 

자 그럼 바로 시작해보자

문제 설명

 

간단하게 설명하면 주어진 문자열(haystack)에서 특정 문자열(haystack)이 있는지, 있으면 몇번째에 위치해 있는지 찾는 문제이다.

 

문제 풀이 방법은 다음과 같이 풀었다.

[0] StringBuffer와 Map을 준비한다. StringBuffer는 subString을 조합하기 위함이고, Map은 만들어진 subString을 key로, 위치를 value로 저장하기 위함이다.

[1] 먼저 0 ~ N(length of needle) - 1 의 subString을 구한다. 해당 subString을 Map에 저장, 이때 subString이 key, index인 0이 value가 된다. 이렇게 저장된 subString과 index는 나중에 needle이 나타난 첫번째 위치를 O(1)의 시간으로 찾기 위해 저장한다.

[2] for-loop를 진행하며, subString의 0번째 char를 제거 한 후 i + N - 1 번째에 위치한 char를 subString에 붙여준다.

그림으로 나타내면 위와 같이 AB, BC , CA가 substring으로 Map에 차곡차곡 저장된다.

[2-1] 이때 , 구해진 subString이 map에 있는 경우 해당 값은 map에 저장하지 않고 생략한다. (가장 빠른 위치를 구해야하기때문에)

[3] 이렇게 Map이 채워지면 마지막엔 map에 needle을 조회함으로써 값이 있는지 없는지 여부를 판단한다.

[4] 그 외에 간단한 short-circuit(logically 종료 조건)을 추가해준다.

 

▶ 이 문제의 핵심은 subString을 Map에 저장함으로써 needle이 있는지 파악할때 O(1)으로 줄일수 있다는 장점이 있다. (물론 subString을 만드는 시간은 O(M)이 걸리겠지만)

 

자세한 코드는 github 과 사진을 남긴다.

 

package com.algoFactory.leetcode;

import java.util.HashMap;
import java.util.Map;

/**
 * User: Minwoo Kang
 * Date: 2020/11/08
 * Time: 1:56 AM
 */

public class Implement_strstr {

    public static void main(String[] args) {
        String stack = "abc";
        String needle = "c";

        int i = strStr(stack, needle);

    }

    public static int strStr(String haystack, String needle) {
        int N = needle.length();
        int M = haystack.length();

        if (N == 0)
            return 0;

        //short circuit - 만약에 찾으려는 단어(needle)의 길이가 주어진 보기(haystack)보다 크다면, 결과는 무조건 -1
        if (N > M)
            return -1;

        Map<String, Integer> map = new HashMap<>();

        //initial buffer
        StringBuffer sb = new StringBuffer(haystack.substring(0, N));
        map.put(sb.toString(), 0);

        for (int i = 1; i + N - 1< M; i++) {
            sb.deleteCharAt(0);
            sb.append(haystack.charAt(i + N - 1));

            if (!map.containsKey(sb.toString()))
                map.put(sb.toString(), i);
        }

        if (!map.containsKey(needle))
            return -1;
        else
            return map.get(needle);
    }
}