[LeetCode] 014.Longest Common Prefix JAVA

Longest Common Prefix - LeetCode

---

❄️ 문제

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 "".

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하여라.
공통 접두사가 없으면 빈 문자열 ""을 반환한다.

---

❄️ 예시

Input: strs = ["flower","flow","flight"]
Output: "fl"

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

---

❄️ 풀이 설명

• 인덱스 오브를 사용할 생각을 처음에 하지 못했다.
• 그러다가 우연히 디스커스에서 indexOf를 사용해서 풀 수 있다는 것을 알게 되어서 그렇게 다시 풀게 되었다.
• 만약 들어오는 문자열 배열의 길이가 0, 즉 배열이 없으면 빈 문자열을 리턴시켜주었다.
• 그리고 비교할 대상으로 result를 선언해주고, 맨 처음 문자열을 담아주었다.

 

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

---

• 문자열 배열의 길이만큼 반복문으로 확인을 해준다.
• indexOf()를 사용하여 해당 문자열이 존재하면 0이 반환되고 아니면 -1이 반환되는 것을 이용하여 문자열을 비교한다.
• 만약 0이 반환되지 않으면, 비교 문자열인 result의 문자열을 뒤에서부터 잘라준다.
• 만약 result 문자열의 길이가 0이면, 빈 문자열을 리턴해 준다.
• 조건문에 해당하지 않고 반복문이 끝나면 남아 있는 result를 출력해준다.

 

public static String longestCommonPrefix(String[] strs) {
   
   ...
   
   for (int i = 1; i < strs.length; i++)
      while (strs[i].indexOf(result) != 0) {
         result = result.substring(0, result.length() - 1);
         if (result.isEmpty()) return "";
      }
   return result;
}

---

❄️  최종 풀이

public static String longestCommonPrefix(String[] strs) {
   if (strs.length == 0) return "";
   String result = strs[0];
   for (int i = 1; i < strs.length; i++)
      while (strs[i].indexOf(result) != 0) {
         result = result.substring(0, result.length() - 1);
         if (result.isEmpty()) return "";
      }
   return result;
}​

---

❄️ 좀 더 빠른 코드

 

• 시간 비교를 했을 때 조금 더 속도가 빨랐던 코드이다.

 

public static String longestCommonPrefix(String[] strs) {
   if (strs == null || strs.length == 0) return "";
   for (int i = 0; i < strs[0].length() ; i++){
      char ch = strs[0].charAt(i);
      for (int j = 1; j < strs.length; j ++) {
         if (i == strs[j].length() || strs[j].charAt(i) != ch)
            return strs[0].substring(0, i);
      }
   }
   return strs[0];
}​

---