[리트코드] LeetCode Longest Common Prefix (Easy) in Java

📑 1. 문제설명

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 "".
Note: All given inputs are in lowercase letters a-z.
 
a-z의 소문자 알파벳으로 단어들로 구성된 배열이 주어졌을 때, 모든 문자열에 공통되는 가장 긴 접두사를 리턴하라.
접두사가 없는 경우에는 빈 문자열을 리턴하라.
 
Example 1

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

 
Example 2

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

 

💡 2. 풀이과정

프로그래머스랑 백준만 알고 있었는데 이웃 brobro332님 블로그 에서 보고 알게 된 코테사이트 LeetCode
 
 
접근 방식

1. 예시 배열 0번 인덱스에 담긴 첫 번째 문자열을 prefix로 설정한다.
2. 다른 문자열들과 비교하며 prefix를 줄여간다. 

    - strs[i].indexOf(prefix) != 0 의 결과가 true 인가? ( prefix가 현재 단어의 접두사가 아니라면)
    - while 문이 실행되서 prefix가 한 글자씩 줄어든다. 
 
최종적으로 남은 prefix가 공통 접두사이다. 
 
 

📌 2-1. indexOf(String s) 메서드란?

이 문제는 indexOf(String s) 메서드로 쉽게 풀 수 있다. 
indexOf(String s)는 문자열 s가 현재 문자열의 어디에서 시작하는지 찾는 메서드이다. 
간단하게 말하면 부분문자열을 반환하는 메서드이다. 
만약 s가 현재 문자열의 시작 부분(접두사) 에 있다면 0을 반환한다.
없다면 -1을 반환하거나, 존재하는 위치의 인덱스를 반환한다.
 
예를 들면 아래와 같다.

System.out.println("flow".indexOf("fl"));   // 0  (맨앞에서 시작함)
System.out.println("flow".indexOf("ow"));   // 2  ("ow"는 2번 인덱스부터 시작)

 
✔️ 문제에서 주어진 배열은 String[] strs = {"flower", "flow", "flight"}; 이다.
초기설정 0번 인덱스에 담긴 flower이 prefix가 된다. 즉, String prefix = "flower"; 이다.
 
✔️ 그 후, 두 번째 요소인 flow와 prefix인 flower를 비교한다.

"flow".indexOf("flower"); // -1 ("flower"는 "flow" 안에 없음)

• "flower"는 "flow" 안에 없으므로 -1 반환
• indexOf(prefix) != 0은 -1 != 0이므로 true
• 즉, "flower"는 "flow"의 접두사가 아니므로 while 루프 실행

while (strs[i].indexOf(prefix) != 0) { 
    prefix = prefix.substring(0, prefix.length() - 1); // 한 글자씩 줄이기
}

• "flower"에서 한 글자씩 줄이면서 "flow"와 접두사가 될 때까지 반복해서 탐색한다.
• "flower" → "flowe" → "flow"

✔️ 마지막으로 세 번째 요소인 flight와 비교한다.

"flight".indexOf("flow") // -1 ("flow"는 "flight" 안에 없음)

• "flow"라는 문자열이 "flight" 안에서 시작되는 인덱스를 찾음
• "flight" 안에 "flow"라는 부분 문자열이 없으므로 -1을 반환한다.
• indexOf(prefix) != 0은 -1 != 0이므로 true라서 while문이 돌아간다.

while (strs[i].indexOf(prefix) != 0) { 
    prefix = prefix.substring(0, prefix.length() - 1); // 한 글자씩 줄이기
}

이제 prefix가 "flow"인 상태에서 위 while 문이 실행된다. 
prefix를 하나씩 줄여가면서 "flight"의 접두사가 되는지 확인하는 과정이다. 

// prefix = "flow"
"flight".indexOf("flow") == -1  // "flight" 안에 "flow"가 없으므로 -1 → while 실행
prefix = "flo"; 

// prefix = "flo"
"flight".indexOf("flo") == -1   // "flo"가 없으므로 -1 → while 실행
prefix = "fl";

// prefix = "fl"
"flight".indexOf("fl") == 0   // "fl"이 "flight"의 접두사이므로 0 → while 종료

"flow"에서 "fl"로 줄인 후에 "flight".indexOf("fl") == 0 (접두사 맞음) → 종료한다.
"flower", "flow", "flight" 세 단어의 가장 긴 공통 접두사는 "fl" 이다. 
 

---

⭐ 3. 정답코드

 
❌ 틀린코드

처음 시도에서는 계속 컴파일 오류가 남

prefix 변수를 선언한게 아니라 변수명을 first로 해 놓고 아래에서는 prefix로 잘못 사용해서 컴파일 오류가 났다. 그래서 String prefix = strs[0];로 변경했다. 그리고 사실 나처럼 코드를 짜서 indexOf(prefix) != 0 로 푸는 경우에는 생각 해 보니까 배열을 정렬 할 필요가 없다. 😂

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

        Arrays.sort(strs); // 사전순 정렬

        String first = strs[0];

        for (int i = 1; i < strs.length; i++) { // 나머지 문자열들이랑 비교
            while (strs[i].indexOf(prefix) != 0) { // prefix가 접두사가 아닐 때
                prefix = prefix.substring(0, prefix.length() - 1); // 한 글자씩 줄이기
                if (prefix.isEmpty()) return "";
            }
        }
        return prefix;
    } 
}

 
정답코드

import java.util.Arrays;

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

        String prefix = strs[0]; // 첫 번째 문자열을 기준으로 설정

        for (int i = 1; i < strs.length; i++) { // 나머지 문자열들과 비교
            while (strs[i].indexOf(prefix) != 0) { // prefix가 접두사가 아닐 때
                prefix = prefix.substring(0, prefix.length() - 1); // 한 글자씩 줄이기
                if (prefix.isEmpty()) return ""; // 접두사가 없으면 종료
            }
        }
        return prefix;
    }
}

👏🏻 좋은 코드

이웃님 블로그에서 가져온 코드 https://brobro332.tistory.com/entry/LeetCode-14-Longest-Common-Prefix-Easy-Java
 
한 마디로, 배열을 먼저 사전순으로 정렬한 후(오름차순 정렬), 첫 번째 단어(first)와 마지막 단어(last)만 비교해서 가장 긴 공통 접두사(prefix)를 찾는 것이다. 왜?

• 중간에 있는 단어들은 첫 번째와 마지막 단어 사이에 있다.
• 그래서 공통 접두사는 첫 번째와 마지막 단어의 접두사보다 짧을 수밖에 없다.
• 따라서 중간 단어들은 스킵해도 문제 없다.

import java.util.Arrays;

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        Arrays.sort(strs); // 정렬하여 사전순으로 배치
        StringBuilder answer = new StringBuilder();
        
        String first = strs[0];
        String last = strs[strs.length - 1];

        for (int i = 0; i < first.length(); i++) {
            if (i < last.length() && first.charAt(i) == last.charAt(i)) {
                answer.append(first.charAt(i));
            } else {
                break;
            }
        }
        
        return answer.toString();
    }
}

 
Arrays.sort(strs)로 사전순으로 정렬한다. 

String[] strs = {"flower", "flow", "flight"}; // 정렬전
Arrays.sort(strs); // 정렬 후: {"flight", "flow", "flower"}

 
배열에서 가장 앞에 오는 단어가 first, 가장 마지막 단어가 last에 저장된다. 

String first = strs[0]; // first = "flight"
String last = strs[strs.length - 1]; // last = "flower"

 

i	first.charAt(i)	last.charAt(i)	비교(==)	실행 후 i값
0	'f'	'f'	✅ 같음	i = 1
1	'l'	'l'	✅ 같음	i = 2
2	'i'	'o'	❌ 다름	반복문 종료함

 
루프가 끝난 후, i = 2 이므로 "flight"와 "flower"의 공통 접두사(prefix) 는 "fl" 이다. 

first.substring(0, i)  // "fl"