📍 1. 문제

LeetCode - Longest Common Prefix

📍 2. 풀이

📌 2-1. 풀이 (Horizontal scanning)

(1) 방법

솔루션의 Horizontal scanning 방법을 이용해 풀이.
과정은 다음과 같다.
Input: strs = ["flower","flow","flight"]
strs.length = 3
String lcd = str0

index = 1

• flow.indexOf(flower) != 0
  lcd = flowe
• flow.indexOf(flowe) != 0
  lcd = flow
• flow.indexOf(flow) == 0

index = 2

• flight.indexOf(flow) != 0
  lcd = flo
• flight.indexOf(flo) != 0
  lcd = fl
• flight.indexOf(fl) == 0

return lcd

시간 O(s) 공간O(1)

(2) 코드

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

(3) 결과

📌 2-2. 풀이 (Vertical scanning)

(1) 방법

공통 접두사를 찾는것이기 때문에 맨 앞부터 비교해가는 풀이.

(2) 코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        
        for(int i = 0; i < strs[0].length(); i++) {
            char std = strs[0].charAt(i);
            for(int j = 0; j < strs.length; j++) {
                if(i == strs[j].length() || strs[j].charAt(i) != std) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }
}

(3) 결과

📍 3. 결론

조그만 문제 하나에 다양한 풀이방법이 존재한다. 시간/공간복잡도 결과도 다 다르고.. 문제해결방법에 초점을 맞추려고 한다.

이 문제의 남은 해결방법은 분할정복, 이진탐색이 남아있다. 추후에 해당 방법으로 풀어봐야겠다.