Longest Common Prefix

첫 번째 단어 전체가 답이라고 가정하고 시작합니다. 그런 다음 두 번째 단어와 글자 단위로 비교해 둘이 공유하는 부분만 남도록 줄입니다. 남은 부분을 세 번째 단어와 비교하고, 이런 식으로 계속합니다. 마지막 단어까지 비교하고 나면 모든 단어에 공통으로 남는 부분이 있습니다.

이 방법이 올바른 이유는 여러 단어의 공통 접두사가 첫 두 단어의 공통 접두사, 그 결과와 세 번째 단어의 공통 접두사, 이런 식으로 구할 수 있기 때문입니다. 각 단계에서는 접두사를 유지하거나 줄이기만 할 수 있습니다. interview, internet, interval, internal의 경우 후보는 두 번째 단어를 비교한 뒤 interview에서 inter로 줄어들고, 이후 그대로 유지됩니다.

각 글자는 최대 한 번 비교되므로 시간 복잡도는 O(S)입니다. 여기서 S는 전체 글자 수입니다. 복사본이 아니라 길이만 저장합니다. 약점은 순서입니다. 첫 199개 단어가 일치하고 마지막 단어의 첫 글자만 다른, 글자 수가 각각 200개인 단어 200개가 있다면, 마지막 단어가 접두사를 아무것도 남지 않게 줄이기 전에 첫 199개 단어 각각의 글자 200개를 모두 비교하게 되어 비교 횟수는 거의 40,000회에 달합니다.

단어를 표처럼 한 번에 한 열씩 살펴보세요. 열 0에는 모든 단어의 첫 글자가, 열 1에는 두 번째 글자가 들어가며, 이런 식으로 이어집니다. 현재 열에서 strs[0]의 글자를 가져와 다른 모든 단어의 같은 위치에 동일한 글자가 있는지 확인하세요. 어떤 단어의 글자가 처음으로 다르거나 해당 열에 글자가 없을 만큼 짧으면, 정답은 해당 열까지의 strs[0]입니다.

정답은 모든 단어가 일치하는 열이 연속해서 이어지는 부분이며, 이 루프는 그 열들을 왼쪽부터 살펴보다가 연속된 부분이 끊기는 첫 번째 열에서 멈춥니다. 끊기는 열이 없다면 strs[0] 자체가 정답입니다. 이 경우 strs[0]는 가장 짧은 단어이거나 가장 짧은 단어와 길이가 같습니다.

루프는 정답 다음 열까지 최대 한 열만 더 읽으므로, 단어가 n개이고 정답의 길이가 L일 때 최대 n × (L+1)번 확인합니다. 또한 단어의 같은 글자를 두 번 읽지 않으므로 O(S)이기도 합니다. 위의 경우처럼 199개 단어는 일치하고 마지막 단어는 첫 글자부터 다르면, 첫 번째 열을 확인한 뒤 멈춥니다. 거의 40,000번이 아니라 199번만 비교합니다.