[Easy] LeetCode - no.14 Longest Common Prefix ⭐ : Java

https://leetcode.com/problems/longest-common-prefix/description/?envType=study-plan-v2&envId=top-interview-150

 

 

문제

주어진 String 배열 strs의 공통된 prefix(접두어)를 구할 것

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.

 

 

 

풀이 - 2가지 풀이 참고 (꼭 다시 풀어볼 것!)

풀이1

  public static String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
      return "";
    }

    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < strs[0].length(); i++) {
      char c = strs[0].charAt(i);

      for (String str : strs) {
        if (str.length() <= i || c != str.charAt(i)) {
          return sb.toString();
        }
      }

      sb.append(c);
    }

    return sb.toString();
  }

• 시간복잡도 : O(N * L) (N은 배열의 길이, L은 첫 번째 문자열의 길이)
• 입력 배열 strs가 빈 배열인지 확인 -> 빈 배열이랴면 "" 반환
• StringBuilder 사용
• 첫번째 문자열 (strs[0]) 을 기준으로 반복
• strs[0]의 i번째 문자를 변수 c에 저장
• 다른 문자열들과 비교
  • 조건1 : str.length() <= i
  • 조건2 : c != str.charAt(i)
• 공통된 문자를 StringBuilder에 추가
• sb.toString() 반환

 

 

풀이2

  public static String longestCommonPrefix2(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);
  }

• 시간복잡도 : O(N log N + L) (배열 정렬이 O(N log N), 문자열 비교가 O(L) - L은 첫 번째 문자열의 길이)
• Arrays.sort() : 배열 정렬
• 첫번째 문자열과 마지막 문자열 비교
• 공통 접두사 찾기
  • while문을 사용하여 첫 번째 문자열과 마지막 문자열의 문자들을 하나씩 비교
  • 첫 번째 문자부터 순차적으로 동일한 문자인지 화인하며, 같을 경우 c를 증가
  • 두 문자가 다르면 while문을 중단하고 비교를 멈춤
• 결과 반환 : 공통 접두사의 길이가 0인 경우 "" 반환, 그렇지 않을 경우 첫 번째 문자열의 0부터 c번째 인덱스까지의 부분 문자열 반환