LeetCode每日一題 最長公共字首

最長公共字首

Description

編寫一個函數來查找字元串數組中的最長公共字首。

如果不存在公共字首，傳回空字元串 ""。

示例 1:

輸入: ["flower","flow","flight"] 輸出: "fl" 示例 2:

輸入: ["dog","racecar","car"] 輸出: "" 解釋: 輸入不存在公共字首。 說明:所有輸入隻包含小寫字母 a-z 。

thought

首先考慮幾個特殊情況，數組長度為0肯定是傳回空字元串了。數組長度為1的時候因為沒有參照對象，是以我們把整個字元串傳回。接下來就是有兩個及更多的情況了：

我們可以考慮把前兩個字元串拿出來做比較，拿出兩個之中長度最小的string，看看另一個參照的string是否有相同字元，用substring做字元截取，不同則繼續往前。

在上面給出的執行個體1中：

1. 拿出"flower","flow"
2. 取長度最小字元串，即"flow"
3. 發現另一個對比對象"flower"相同的substring是否相同。發現"flower"也含有"flow"
4. 如果沒有則繼續向前，直到最後一位。沒有傳回空字元串

code

class Solution {
     public String longestCommonPrefix(String[] strs) {
         String pre = "";
         if(strs.length == 0) {
             return "";
         }
         if(strs.length == 1) {
             return strs[0];
         }
         pre = help(strs[0],strs[1]);
         if(pre == null) {
             return "";
         }
         for(int i = 2;i < strs.length; i++){
             pre = help(pre,strs[i]);
             if(pre == null){
                 return "";
             }
         }
         return pre;
     }
 ​
 ​
     private String help(String s1,String s2) {
         int len = Math.min(s1.length(),s2.length());
         for(int i = len;i>0;i--){
             String t = s1.substring(0,i);
             if(t.equals(s2.substring(0,i))){
                 return t;
             }
         }
         return null;
     }
 }
           

done

感謝。 2020-08-21