最长公共前缀-Java-蒲公英云

最长公共前缀-Java

心已赠人 2021-11-23 02:54 402阅读 0赞

//最长公共前缀
//题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
//示例 1:
//输入: [“flower”,”flow”,”flight”] 输出: “fl”
//示例 2:
//输入: [“dog”,”racecar”,”car”] 输出: “”
//解释: 输入不存在公共前缀。
//说明:所有输入只包含小写字母 a-z。
//解题思路：
//1、因为是所有字符串都公共的前缀，所以首先假设这个公共前缀是第一个字符串;
//2、如果对比第二个字符串出现不相等与第一个字符串，则进行缩短，直到是两者的公共前缀，再比较下一个字符串.
//3、如果出现将前缀字符串缩短为空，则无需继续判断，直接返回””
//int indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
//int indexOf(String str, int fromIndex): 返回从 fromIndex位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。

package pratice725;
import java.util.ArrayList;
//最长公共前缀
//题目描述：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。
//示例 1:
//输入: [“flower”,”flow”,”flight”] 输出: “fl”
//示例 2:
//输入: [“dog”,”racecar”,”car”] 输出: “”
//解释: 输入不存在公共前缀。
//说明:所有输入只包含小写字母 a-z。
//解题思路：
//1、因为是所有字符串都公共的前缀，所以首先假设这个公共前缀是第一个字符串;
//2、如果对比第二个字符串出现不相等与第一个字符串，则进行缩短，直到是两者的公共前缀，再比较下一个字符串.
//3、如果出现将前缀字符串缩短为空，则无需继续判断，直接返回””
//int indexOf(String str): 返回指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
//int indexOf(String str, int fromIndex): 返回从 fromIndex位置开始查找指定字符在字符串中第一次出现处的索引，如果此字符串中没有这样的字符，则返回 -1。
public class LCSpre {
public static String longestCommonPrefix(String[] strs) {
int strsl = strs.length;
if(strs==null || strs.length==0) return “”;
String pre = strs[0];
for(int i=1;i<strsl;i++){
if(strs[i]==null || strs[i].length()==0) return “”;
while(strs[i].indexOf(pre) !=0){
pre = pre.substring(0,pre.length()-1);
}
if(pre.isEmpty())
return “”;
}
return pre;
}
public static void main(String[] args) {
String strs[] = {“dog”,”racecar”,”car”};
System.out.println(“result: “+longestCommonPrefix(strs));
}
}