[LeetCode] 14. Longest Common Prefix (Python)

문제 원문 링크 : leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

이 문제는 굉장히 쉽다. Easy라고 붙어있는 글씨 그대로다.

먼저 가장 간단하게 떠올릴 수 있는 vertical scanning으로 풀어보겠다.

---

1. Vertical scanning

1. 주어진 string list를, 각 원소의 길이를 기준으로 오름차순 정렬한다.

(이때 정렬기준 설정을 위해 lambda 함수를 이용한다.)

(이와 같이 정렬을 하는 이유는, 가능한 최대의 common prefix는 list 내에서 가장 짧은 원소이기 때문이다.)

 

2. 가장 짧은 원소를 기준으로, 다른 원소들을 차례대로 순회한다.

 

3. 매 iteration마다 해당 index의 character가 가장 짧은 원소의 character와 같은지 확인한다.

그리고 common prefix가 더이상 형성되지 않는 index를 찾아, 그 부분까지 substring해서 return한다.

 

이를 코드로 구현하면 아래와 같다.

이 algorithm의 time complexity는 원소들의 총 개수를 n, 가장 짧은 원소의 길이를 m라고 했을 때,

O(nlogn + mn)이 된다.

(sort 함수의 time complexity와 nested for loop의 time complexity를 더하면 된다.)

---

2. Binary search

또 다른 방법으로는 binary search(이진 탐색)을 이용하는 방법이 있다.

 

1. 첫번째 원소는 target 변수로, 나머지 원소들은 remains 변수로 분리한다.

(이때 원소가 하나 뿐이라면, 그 자체가 common prefix가 되므로 따로 처리한다!)

 

2. left는 0으로, right은 target의 마지막 인덱스(len(target) - 1)로 초기화한다.

그리고 mid는 (left+right) // 2로 초기화 한다.

 

3. left <= right 때까지, target[0 : mid+1]이 common prefix인지 확인하는 과정을 반복한다.

 

이를 코드로 구현하면 아래와 같다.

이 algorithm의 worst case는 원소들의 총 개수를 n라고 했을 때, 모든 string 원소의 길이가 m으로 동일한 경우이다.

 

★ 왜 저 경우가 worst case인가?

→ 중간에 멈추는 경우 없이, loop를 돌 때마다 string 처음부터 끝까지 character 비교 연산을 다 해봐야 하기 때문!

 

따라서 time complexity는 binary search 자체의 time complexity인 O(log m)과,

매 iteration마다 진행하게 되는 character 비교 연산의 time complexity를 곱하면 된다.

(worst case에서 character 비교 연산의 time complexity는 O(mn)이다)

따라서 O(m*n*log n) !

 

이 외에도 horizontal scanning, divide and conquer 등으로도 풀 수 있다.

(자세한 건 아래의 reference 참고!!)

---

Code

https://github.com/changyeon2/Algorithm/tree/master/leetcode/problem%2014/python3

---

References

1. leetcode.com/problems/longest-common-prefix/solution/

2. cs.stackexchange.com/questions/9523/is-omn-considered-linear-or-quadratic-growth

3. wayhome25.github.io/python/2017/06/14/time-complexity/