LeetCode 14. 最长公共前缀 - Easy
LeetCode 14. 最长公共前缀 - Easy
贺biubiu
发布于 2020-11-25 15:08:21
发布于 2020-11-25 15:08:21
14. 最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。说明:
- 所有输入只包含小写字母 a-z 。
暴力解法一
入上草图，说思路：
- 基本校验，输入数组为空直接 return，输入数组只有一个时，同理直接 return；
- 取数组中第一个为基数，依次判断数组中 char 是否相等，同时更新数组比对结果，也就是基数内容；当基数为空时，直接 return。
这里首要明确，最长公共，也就是从数组中的每一个开始比对，如果出现不一样则停止比对。当初我就是这里犯了嘀咕。
这里附上代码：
fun longestCommonPrefix(strs: Array<String>): String {
var resultStr = ""
if (strs.isEmpty()) {
return resultStr
}
if (strs.size == 1) {
return strs[0]
}
resultStr = strs[0]
for(str in strs){
var j = 0
while (j < resultStr.length && j < str.length){
if(str.toCharArray()[j] != resultStr.toCharArray()[j]){
break
}
j++
}
resultStr = resultStr.substring(0,j)
if(resultStr.isEmpty()){
break
}
}
return resultStr
}消耗情况：
暴力解法二
在 Debug 过程中，突然发现第一种解法的循环比对是从头开始的。这块其实应该是从数组第一位开始，因为一开始就选取了数组第 0 位作为基数进行对比，这里改造下代码，减少一层循环：
fun longestCommonPrefix2(strs: Array<String>): String {
var resultStr = ""
if (strs.isEmpty()) {
return resultStr
}
if (strs.size == 1) {
return strs[0]
}
resultStr = strs[0]
for(i in 1 until strs.size){
var j = 0
while (j < resultStr.length && j < strs[i].length){
if(strs[i].toCharArray()[j] != resultStr.toCharArray()[j]){
break
}
j++
}
resultStr = resultStr.substring(0,j)
if(resultStr.isEmpty()){
break
}
}
return resultStr
}消耗情况：
暴力解法三
突然想到为什么每次都要 toCharArray() 呢？我直接取对应的值不好么？
再次改造下代码：
class Solution {
fun longestCommonPrefix(strs: Array<String>): String {
var resultStr = ""
if (strs.isEmpty()) {
return resultStr
}
if (strs.size == 1) {
return strs[0]
}
var len = strs.size
Arrays.sort(strs)
for (i in strs[0].indices){
if(strs[len-1][i] == strs[0][i]){
resultStr += strs[0][i]
}else{
break
}
}
return resultStr
}
}消耗情况：
学习下大佬解法 - 排序法
思考以及通过 Debug 后得出思路如下：
- 基本校验同上，不再累述；
- 对数组进行排序，对比第一个和最后一个。复杂度我猜测应该基于数组的排序这块。
简单举个例子：
现提供数组如下：
- {"flower", "flow", "flight"}
经过排序后，变成：
- {"flight", "flow", "flower"}
随后直接对比数组第一个和最后一个即可。最终得出最长公共前缀为：
- fl
贴一下代码部分：
fun longestCommonPrefix3(strs: Array<String>): String {
var resultStr = ""
if (strs.isEmpty()) {
return resultStr
}
if (strs.size == 1) {
return strs[0]
}
val len = strs.size
Arrays.sort(strs)
for (i in strs[0].indices){
if(strs[len-1][i] == strs[0][i]){
resultStr += strs[0][i]
}else{
break
}
}
return resultStr
}消耗情况：
这种解法有点疑惑
在 LeetCode 中，最优解提示我是如下这种方案。但是实际提交后，并没有发现哪儿最优。
而且 LeetCode 相同的代码段提交两次，时间以及消耗并不一样，很奇怪。简单说下这种解法吧。
- 同样的校验，只是另外对数组一个元素进行了判空；
- 首先获取数组中最短的长度；
- 随后获取到相同索引；
- 最后截取返回
简单举个例子：
给定数组如下：
- {"flower", "flow", "flight"}
此处忽略前期基本校验。
获取提供数组中最短长度，也就是 flow 4 位。然后依照数组第一个进行比对，三者相同内容的索引为 1，也就是 fl。最后直接 return 裁剪此索引即可。
以下附上代码：
fun longestCommonPrefix4(strs: Array<String>): String {
if (strs.isEmpty()) {
return ""
}
if (strs.size == 1) {
return if(strs[0].isEmpty()) "" else strs[0]
}
// 获取输入数组中最短长度
var min = Int.MAX_VALUE
for(str in strs){
if(min > str.length){
min = str.length
}
}
// 获取最后一次相同的位置
var isl = true
var index = 0
while (index < min){
for(i in strs.indices){
if(strs[0][index] != strs[i][index]){
isl = false
break
}
}
if(!isl){
break
}
index++
}
return strs[0].substring(0,index)
}消耗情况：
为了避免大佬喷我，此处放出此解法地址：
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-11-16，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读