[LeetCode] (Easy) 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 "".

 

Example 1:

 

Input: strs = ["flower","flow","flight"]
Output: "fl"

 

Example 2:

 

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

정답 코드

---

<  내 정답 코드  >

 

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        int smallestLength = strs[0].length();

        for (int i = 1; i < strs.length; i++) {
            if (smallestLength > strs[i].length()) {
                smallestLength = strs[i].length();
            }
        }

        outer:
        for (int i = 0; i < smallestLength; i++) {
            char ch = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (ch != strs[j].charAt(i)) {
                    break outer;
                }
            }
            sb.append(strs[0].charAt(i));
        }

        return String.valueOf(sb);
    }
}

 

<  타인 답변 코드  >

 

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);
            }
        }
        
        return prefix;
    }
}

이것을 주의하자!

---

-  일단 String[ ] 내 문자열 중에서 가장 짧은 문자열의 길이만큼만 알파벳을 비교하면 되니 가장 짧은 길이를 구했다. 그리고 비교 대상을 strs [0] 원소로 한 다음, 해당 원소의 알파벳과 다른 원소의 알파벳들을 비교했다. 모두 동일하면 StringBuilder 객체에 붙이고, 아니면 반복문을 종료한다. 시간 효율이 나쁘지 않다!

 

-   타인 답변 코드를 보면 이 문제의 열쇠는 " string.indexOf ( ) " 메서드이다.  indexOf ( ) 의 성질을 잘 알면 풀 수 있다.

 

-  먼저 매개변수가 값이 없는 경우를 걸러낸다. 그리고 가장 첫 단어를 '기준'으로 삼는다. strs [ ] 내 원소의 수 만큼 반복할건데, while 문을 통해 어디까지 동일한지 판단한다.   비교 단어.indexOf( 기준 단어 ) 을 실행했을 때 기준 단어가 비교 단어보다 크거나, 비교 단어의 첫 부분부터 기준 단어가 동일하지 않으면 0 이 될 수 없다. 그러면 기준 단어를 string.substring( ) 으로 뒤 부터 하나씩 잘라낸 후 다시 비교한다.

 

-  혹시나 아예 다른 단어라서 기준 단어 다 잘려나가 "" 이 되어버린다면 어떻게 될까?  비교 단어.indexOf( "" ) 의 반환값은 0 이다. 따라서 오류가 나지 않는다.