LeetCode - 14. Longest Common Prefix(String)*

문제

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성합니다.

공통 접두사가 없으면 빈 문자열 "을(를) 반환합니다.

https://leetcode.com/problems/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.

풀이

자바입니다.

• indexOf() 를 사용해서 공통된 문자열이 있나 찾는다.
• substring 을 사용해서 문자열을 자른다.

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

}

다른 풀이를 보던 중 참신한 방법이 있어서 코드를 남깁니다.
Array.sort()를 사용해서 배열을 정렬하고 정렬된 처음 값과 마지막 값을 비교하는 방식입니다.

https://leetcode.com/problems/longest-common-prefix/discuss/721752/Java-100-just-compare-two-strings

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

	}

}