문제

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

input

strs = ["flower","flow","flight"]

output

"fl"

---

input

strs = ["dog","racecar","car"]

output

""

Explanation

There is no common prefix among the input strings.

제약 조건

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lowercase English letters.

문제 분석

문자열 배열의 요소들 중 가장 긴 공통 접두사 문자열을 찾는 문제이다.
공통 접두사 문자열이 없으면 "" 를 반환한다.

가장 긴 공통 접두사

• 모든 요소들이 같은 접두사 문자열을 가지고 있다.
• 모든 요소들이 가지고 있는 공통된 접두사 중 가장 긴 접두사를 반환한다.

배열 정렬 후 첫번째 요소와 마지막 요소의 공통된 접두사는, 정렬된 배열 내의 모든 요소들이 공유하는 접두사 이다.

손으로 풀어보기

1. 위 Example 를 기준으로 입력값으로 들어 온 strs 배열을 정렬하게 된다면
   "flight", "flow", "flower" 순이 될 것이다.
2. 첫번째 요소와 마지막 요소를 꺼낸다.
3. 길이가 작은 요소의 길이 만큼 순회하며 문자를 비교한다.
4. 문자가 같으면 반복이 계속 되고, 같지 않으면 반복이 종료된다.
5. 반복이 종료될 시점의 i 를 구해서 첫번째 요소의 subString 을 만들어 반환한다.

슈도코드

public class Solution {
	public String longestCommonPrefix(String[] strs) {
		strs 엣지 케이스를 처리한다. (null 이거나 길이가 0 일 때)
		strs 배열을 정렬한다.
		첫번째 요소 저장 할 변수 선언
		마지막 요소 저장 할 변수 선언
		공통 접두사의 길이 저장 할 변수 선언
		for(두 요소 중 길이가 짧은 길이 까지) {
			if(첫번째 요소의 i 번째 문자 == 마지막 요소의 i 번째 문자) {
				접두사 길이 변수++;
			} else {
				문자가 다른 경우 즉시, 종료
			}
		}
		return 접두사 길이 변수 == 0 ? "" : 첫번째 요소의 0 부터 접두사 길이변수 까지의 subString 반환;
	}
}

구현

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
			return "";
		
		Arrays.sort(strs);
		
		String first = strs[0];
		String last = strs[strs.length - 1];
		int prefix = 0;
		
		for (int i = 0; i < Math.min(first.length(), last.length()); i++) {
			if (first.charAt(i) == last.charAt(i)) {
				prefix++;
			} else {
				break;
			}
		}
		
		return prefix == 0 ? "" : first.substring(0, prefix);
    }
}