[LeetCode] 14. Longest Common Prefix

Problem

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.

Constraints:

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

Solution

Logic

• 문제에서 다음과 같은 규칙을 찾을 수 있다.

  1. 가장 긴 Prefix는 배열 strs 속 가장 짧은 문자열의 길이와 같거나 짧다.
  

• 따라서 배열 strs 속 가장 짧은 문자열을 기준으로 배열 속 다른 요소들과 비교하여 문제를 해결할 수 있다.

  Code(Bottom-up)

  class Solution {
    public String longestCommonPrefix(String[] strs) {
        String minStr = strs[0];
        for (int i = 1; i < strs.length; i++)
            minStr = strs[i].length() < minStr.length() ? strs[i] : minStr;
  
        String result = "";
        for (int i = 0; i < minStr.length(); i++) {
            for (int j = 0; j < strs.length; j++)
                if (minStr.charAt(i) != strs[j].charAt(i))
                    return result;
            result += minStr.charAt(i);
        } return result;
    }
  }
  

  Code(Top-down)

  class Solution {
    public String longestCommonPrefix(String[] strs) {
        String minStr = strs[0];
        for (int i = 1; i < strs.length; i++)
            minStr = strs[i].length() < minStr.length() ? strs[i] : minStr;
  
        while (0 < minStr.length()) {
            for (int i = 0; i < strs.length; i++) {
                if (!strs[i].startsWith(minStr)) {
                    minStr = minStr.substring(0, minStr.length() - 1);
                    break;
                } else if (i == strs.length - 1)
                    return minStr;
            }
        } return "";
    }
  }
  

  Time Complexity

• 배열 strs의 길이를 n이라고 할 때, 아래 반복문에서 n - 1의 시간, 즉 O(n)의 시간 복잡도를 가진다.

  for (int i = 1; i < strs.length; i++)
    minStr = strs[i].length() < minStr.length() ? strs[i] : minStr;
  

• 아래의 반복문에서는 최선의 경우와 최악의 경우로 나누어 볼 수 있다. ```java for (int i = 0; i < minStr.length(); i++) { for (int j = 0; j < strs.length; j++) if (minStr.charAt(i) != strs[j].charAt(i)) return result; result += minStr.charAt(i); }

최선의 경우 :

배열 strs의 길이가 1인 경우 그리고

문자열 minStr의 길이가 0인 경우

-> O(1)

최약의 경우 :

배열 strs의 길이가 200인 경우 그리고

문자열 minStr의 길이가 200인 경우

-> O(n^2) ```

• 첫 번째 반복문에서 O(n)의 시간 복잡도를 가진다는 것을 감안했을 때 이 솔루션은 최선의 경우에는 O(n), 최악의 경우에는 O(n^2)의 시간 복잡도를 가진다.