#73 Coding面試 LeetCode#14 Longest Common Prefix

原題目網址是 https://leetcode.com/problems/longest-common-prefix/description/

這一題在 LeetCode 的難易度分類屬於簡單級,題目的意思是你會得到一個 string array,然後你得從這個 string array 裡面找到最長從頭開始的共同子字串.在題目裡有給了簡單的範例,例如 Input: ["flower","flow","flight"] , 則答案就是 "fl".如果找不到合適的子字串,就直接回傳空字串.同時題目也告訴你,input 字串只有 a 到 z 之間的小寫字母,不會有其他的符號,這個條件大大降低了答案的難易度,因為可以少一些大小寫辦別或特殊字元或文化上的處理.

解法的邏輯也相對單純.找出最短長度的字串,以它為基礎,然後去比對每一字串從頭開始的字母,以此類推做到有一個字母是不符合條件或是最短長度已經到達.

參考的程式碼如下:



這解法的時間複雜度是 O(n2),空間複雜度是 O(n).也許有更快速的解法等待你的尋找.

Help it helps,
Share: