Leetcode14 Longest Common Prefix

문제

https://leetcode.com/problems/longest-common-prefix/description/

 

 

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.

 

 

접근법

여러 문자열이 있을 때,
모든 문자열이 공통으로 가지고 있는 가장 앞부분(접두사)을 구하는 문제.

 

접근 구조

1. 기준 문자열 하나를 정한다 (strs[0])
2. 그 문자열의 문자 위치(j) 를 0부터 하나씩 본다.
3. 같은 위치의 문자가 모든 다른 문자열에서도 같은지 확인한다.
4. 하나라도 다르거나, 문자열 길이가 부족하면? 거기서 종료
5. 그 직전까지가 정답

• 지금 j번째 문자가 모든 문자열에 존재하는지
• 모두 같은 문자인지

확인해봐야함.

 

의사코드

기준 문자열 first

for (문자 위치 j):
    기준 문자 c = first[j]

    for (각 문자열 i):
        if (i번째 문자열이 j번째 문자를 못 가지거나
            j번째 문자가 c와 다르면):
            return first[0 ~ j)

return first

 

 

포인트

1. 배열 인덱스 vs 문자열 인덱스

2. substring(0, j) 사용.

-> 0번째부터 j 직전까지

 

 

제출 코드

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

        String first = strs[0];

        for (int j = 0; j < first.length(); j++) {
            char c = first.charAt(j);

            for (int i = 1; i < strs.length; i++) {
                if (j >= strs[i].length() || strs[i].charAt(j) != c) {
                    return first.substring(0, j);
                }
            }
        }
        return first;
    }
}