Java查询字符串数组nums中最长的公共前缀子串,如果不存在公共前缀返回字符串**
时间: 2023-08-01 14:08:04 浏览: 50
可以使用水平扫描法来解决此问题。具体实现步骤如下:
1. 首先判断数组是否为空或者长度为0,如果是则返回字符串 "**"。
2. 取数组中的第一个字符串作为初始的公共前缀子串。
3. 遍历数组中的每个字符串,依次比较每个字符串和公共前缀子串的每个字符是否相等,如果不相等则将公共前缀子串的长度缩短,直到公共前缀子串和该字符串的前缀相同为止。
4. 如果公共前缀子串的长度为0,则说明不存在公共前缀,返回字符串 "**"。
5. 如果遍历完数组中的所有字符串后,公共前缀子串的长度不为0,则说明找到了最长的公共前缀子串,返回该子串即可。
下面是Java代码实现:
```
public static String longestCommonPrefix(String[] nums) {
if(nums == null || nums.length == 0) {
return "**";
}
String prefix = nums[0];
for(int i = 1; i < nums.length; i++) {
while(nums[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if(prefix.isEmpty()) {
return "**";
}
}
}
return prefix;
}
```
注意,该算法的时间复杂度为O(mn),其中m为数组中字符串的平均长度,n为数组的长度。