[LeetCode] #14 Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.
If there is no common prefix, return an empty string "".

가장 긴 접두사를 구하는 문제다. 

 

이런저런 방법을 써봤는데 도저히 감이 안 잡혀서 솔루션을 참고했다.

댓글이 웃겨서 캡쳐. 어떻게 이게 쉬운 등급이냐고?? 🤣

 

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
            }
            if(prefix.isEmpty()){
                return "";
            }
        }
        return prefix;
    }
}

1. 만약 배열 strs의 길이가 0이라면 빈 배열이 들어온 것이므로 당연히 공통된 접두사가 없을 것이다. 빈 문자열을 리턴한다.
   
   
2. 스트링 타입의 prefix 변수를 생성하고 strs 배열의 첫 번째 값을 넣는다. 
   
   
3. 이제부터 for문을 돌린다. strs 배열의 첫번째 값 (인덱스 0)은 이미 prefix 변수에 들어가 있으므로, 이와 비교하기 위해서는 인덱스 1번부터 시작하여 배열의 길이만큼 반복한다. 
   1. while문: prefix와 strs[i]번째 값이 동일해질 때까지 prefix를 한 글자씩 자른다.
      예를 들어, strs[1]이 flow, prefix가 flower라면 strs[1].indexOf(prefix)의 반환값은 -1이 된다. 
      그러면 substring 메소드를 이용하여 prefix 문자열을 자른다. 시작 인덱스: 0 / 끝 인덱스: (prefix의 총길이 -1)
      기존 prefix는 flower였으니, 한글자가 잘려서 flowe가 된다. 
   2. 다시 while문으로 돌아가서, strs[1]이 flow, prefix가 flowe이니 반환 값은 여전히 -1이다. substring 메소드가 다시 실행된다. 
   3. 다시 while문, 현재는 strs[1] flow, prefix가 flow! 그렇다면 indexOf의 반환 값은 0이 되어 while문을 빠져나오게 된다. 
   4. i의 값이 올라가고.. strs[2]에는 flight가 있다고 하면, 현재 prefix인 flow와는 indexOf의 반환 값이 계속 -1이 나온다. 동일한 접두사인 fl만 prefix에 남을 때까지 while문이 계속 반복된다. 
4. 만약 동일한 접두사가 없어 while문이 계속 실행되어 prefix에 남은 글자 수가 없게 된다면 "" 빈 문자열이 반환된다. 
   
   
5. prefix를 리턴하고 종료한다.