❄️ 문제
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];
}
'알고리즘 > LeetCode' 카테고리의 다른 글
[LeetCode] 016. 3Sum Closest JAVA (0) | 2023.01.05 |
---|---|
[LeetCode] 015. 3Sum JAVA (0) | 2023.01.05 |
[LeetCode] 013. Roman to Integer JAVA (0) | 2022.12.30 |
[LeetCode] 011.Container With Most Water JAVA (0) | 2022.12.26 |
[LeetCode] 012. Integer to Roman JAVA (0) | 2022.12.23 |
댓글