編寫一個函數來查找字元串數組中的最長公共字首。(每天一道防止癡呆)
題目:
編寫一個函數來查找字元串數組中的最長公共字首。
如果不存在公共字首,傳回空字元串 ""。
示例 1:
輸入: ["flower","flow","flight"]
輸出: "fl"
示例 2:
輸入: ["dog","racecar","car"]
輸出: ""
解釋: 輸入不存在公共字首。
說明:
所有輸入隻包含小寫字母 a-z 。
來源:力扣(LeetCode)
連結:https://leetcode-cn.com/problems/longest-common-prefix
著作權歸領扣網絡所有。商業轉載請聯系官方授權,非商業轉載請注明出處。
package com.wxp.Dynamicprogramming;
/**
* 字元串的最長公共字首
* @author amarsoft
*
*/
public class Leetcode14 {
public static void main(String[] args) {
String [] s = {"dog","racecar","car"};
String result = longestCommonPrefix(s);
System.out.println(result);
}
public static String longestCommonPrefix(String[] strs) {
if(strs.length==0) {
return "";
}
String temp = strs[0];//取第一個字元數組為暫存
for (int i = 0; i < strs.length; i++) {
int j =0;
//循環比較第二個和第一個比較之後的公共部分,在和第三個比較就是整個數組中字元串最長的公共部分。
for(;j<temp.length()&&j<strs[i].length();j++) {
if(temp.charAt(j)!=strs[i].charAt(j)) {
break;
}
}
temp = temp.substring(0, j);
}
return temp;
}
/**
* 方法二,運作時間較短
* @param strs
* @return
*/
public String longestCommonPrefix2(String[] strs) {
if(strs.length==0) return "";
String str=strs[0];
for(int i=1;i<strs.length;i++){
while(strs[i].indexOf(str)!=0){
str=str.substring(0,str.length()-1);//如果字元串不比對則長度減一繼續
}
}
return str;
}
方法三:建構trie樹
}