LeetCode 14:Longest Common Prefix


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


 
 

一个函数,传入一个字符串数组,返回所有数组元素里公共前缀的最长子串

可以以第一个字符串为基准,遍历strs[0]的所有字符,然后每次拿字符和同位置的其它字符串的字符进行对比,如果有不相同的,前面的子串即为所求

但是很容易少了一个条件,当strs[0]不是最短的字符串时候,如果前面都一样,肯定有其它字符串先遍历到末尾,这时候应该就直接返回,否则就越界

package com.maoxiaomeng;

/**
* @author lihui
* @date 2018/3/26 12:31
*/

public class Solution {
/**
* "lihuia", "lihuib", "lihuiab", "lihuic"
*
* l i h u i a
* l i h u i b
* l i h u i a b
* l i h u i c
* @param strs
* @return
*/
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
for (int i = 0; i < strs[0].length(); i++) {
char c = strs[0].charAt(i);
for (int index = 1; index < strs.length; index++) {
if (i == strs[index].length() || c != strs[index].charAt(i)) {
return strs[0].substring(0, i);
}
}
}
return strs[0];
}
}

另一种更简单的方法,同样以第一个字符串元素为基准,先看整个字符串strs[0]是否在其它字符串中,然后去掉最后一个字符验证,然后去掉最后两个,……,直到substring在所有的字符串前缀里

Java源码如下

package com.maoxiaomeng;

/**
* @author lihui
* @date 2018/3/26 12:31
*/

public class Solution {
/**
* "lihuia", "lihuib", "lihuiab", "lihuic"
* @param strs
* @return
*/
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) {
return "";
}
String maxStr = strs[0];
for (int i = 1; i < strs.length; i++) {
while (strs[i].indexOf(maxStr) != 0) {
maxStr = maxStr.substring(0, maxStr.length() - 1);
}
}
return maxStr;
}
}

比较直接

发表回复