14.Longest Common Prefix

【题目】

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string"".

編寫一個函數來查找字符串數組中的最長公共前綴。

如果不存在公共前綴，返回空字符串 ""。

Example 1:

Input: 
["flower","flow","flight"]

Output:
 "fl"

Example 2:

Input: 
["dog","racecar","car"]

Output:
 ""

Explanation:
 There is no common prefix among the input strings.

【思路】

Longest Common Prefix 最長共同前綴，因為是前綴所以他一定是從第一個位置的字串開始比較，

然後因為一定要共有，所以每次取第一個值去比較後幾個就好了，跑個兩個迴圈試試看，記住下列兩種點：

1：兩陣列比對時，第一個指標的字串錯了就趕快回覆空字串了，因為這就是錯! 錯! 錯!

2：暫存變數的控制

【解法】

☆JAVA

Java這邊比較單純，應用好indexOf可以迅速比對字串間是否符合

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String temp = "";
        if(strs != null && strs.length >0){    
            temp = strs[0];                                            //先用第一個字串來比對
            if(temp == ""){return "";}                                 //如果是空字串就不要玩了
            for(int i = 1 ; i<strs.length ; i++){                      //從次一個開始比  
                while (strs[i].indexOf(temp) != 0)                     //這邊應用indexOf 比較 如果他不是從第一個查到位置 != 0  
                    temp = temp.substring(0, temp.length() - 1);       //我們就減少他最後一個字串 直到比到為止
            }
        }
        return temp;
    }
}

☆Python

老實說這段寫起來蠻亂的因為實際上卡了一段時間，後來才想說算了就用許多變數來控制吧

class Solution:
    def longestCommonPrefix(self, x):
        # 用這個陣列當作範例Input值 ["flower","flow","flight"]
        result = "";                                        #回傳答案 要控制好該值
        compTemp = "";                                      #當下比對的[陣列-A]
        if(x is not None and len(x) != 0):                  #防呆
            result = str(x[0]);                             #既然有長度 那初始值就取第一個
            for i in range(1,len(x)):                       #比對陣列迴圈-因為我們 已經取第一個了 然長度從第二個開始 就是指標 1
                temp = x[i];                                #比對陣列 第一次是 flow 再來是 flight
                for j in range(min(len(result),len(temp))): #用陣列-A和比對陣列比較誰最短 就用此長度 不然怕溢出陣列指標
                    if(result[0] != temp[0]):               #第一個指標的字元錯了就回覆空字串
                        return "";
                    if(result[j] == temp[j]):               #如果對的話 
                        compTemp = compTemp + temp[j];      #就將其字元存入暫存 compTemp
                result = compTemp;                          #然後塞到 result 內 , 這樣之後就用result當作 陣列-A 去做後續..
                compTemp = '';                              #如此一來我們都是用 公共前綴 來比較 而不是陣列與陣列比較
        return  result;

14. Longest Common Prefix