Devide and Conquer

[Algorithm][LCP] LeetCode 14 - Longest Common Prefix

알고리즘 분류 Longest Common Prefix 시간 복잡도 \( O(mn) \) 문제 링크 https://leetcode.com/problems/longest-common-prefix/ 이번 문제의 알고리즘 종류는 LCP(Longest Common Prefix)입니다. LeetCode에서 Easy 난이도의 문제로 등록되어 있지만, 여러가지 문제 풀이 방법들이 존재합니다. 저는 여러가지 방법 중 분할기법(Devide and Conquer)을 사용했습니다. String 리스트가 주어질 때 리스트 길이가 1이 될 때까지 index를 계속 두 그룹으로 나눠줍니다. 재귀 함수를 사용하여 쉽게 구현할 수 있습니다. 해당 재귀 함수는 String끼리 비교하며 LCP를 구하며 가장 처음의 함수까지 올라옵니다. ..