Longest Common Prefix
December 22, 2024
문제 링크
해결 방법 1
function longestCommonPrefix(strs: string[]): string {
let ans = "";
let strToCompare = "";
strs.forEach((str, idx, arr) => {
if (idx === 0) {
strToCompare = str;
ans = strToCompare;
} else if (str || str === "") {
strToCompare = findCommonPrefix(strToCompare, str);
ans = strToCompare;
}
});
return ans;
function findCommonPrefix(str1: string, str2: string): string {
let commonPrefix = "";
for (let i = 0; i < Math.min(str1.length, str2.length); ++i) {
if (str1[i] === str2[i]) {
commonPrefix += str1[i];
} else {
break;
}
}
return commonPrefix;
}
}문자열 두 개를 인자로 받아서 공통 접두사를 반환하는 함수를 사용했다. else break은 접두사만 반환하도록 하기 위한 것인데, ["cir", "car"]와 같은 테스트 케이스에서 "cr"이 반환되지 않도록 방지한다. 그리고 주어진 문자열 배열을 차례로 순회하면서 위 함수 이용해 모든 문자열의 공통 접두사를 찾아낸다.
해결 방법 2
class Solution:
def longestCommonPrefix(self, v: List[str]) -> str:
ans=""
v=sorted(v)
first=v[0]
last=v[-1]
for i in range(min(len(first),len(last))):
if(first[i]!=last[i]):
return ans
ans+=first[i]
return ans다른 분의 풀이다. 내가 풀었던 방법보다 훨씬 간단하다. 이걸 보고 내 방식의 방향이 많이 돌아갔음을 알았다. 주어진 문자열 배열을 정렬할 생각을 못했다. 보면 정렬한 뒤 가장 짧은 문자열과 긴 문자열만 비교하면 된다. 어차피 가장 짧은 문자열에 공통 접두사가 없으면 말짱 도루묵이기 때문이다. 좋은 방식이다.