算法第3天

leetcode 14. 最长公共前缀 simple

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

输入: ["flower","flow","flight"]
输出: "fl"

输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。

---

解题思路

解法一: 挨个比较

1. 首先要注意边界条件, 数组为空的情况
2. 先找到数组里最短的字符串,因为题目是求最短前缀,必须先找最短的字符串
3. 拿最短字符串与数组里每一个字符串的每一个字符进行比较. 如果不相等则截取,即获取最短前缀.
4. 注意这里是最外层循环是最短的字符串循环, 然后里层循环是数组循环, 挨个字符串进行比较. 也就是查看所有的字符串与最短的字符串是否一致.如果出现不一致则截取返回.

func LongestCommonPrefix(strs []string) string {
    l := len(strs)
    if l == 0 { //边界条件
        return ""
    }
    short := strs[0]
    //从数组里查找到最小字符串.
    for i := 1; i < l; i++ {
        if len(short) > len(strs[i]) { //只要存在比第一个字符还短的则进行赋值操作.
            short = strs[i]
        }
    }
    //如果最短字符串长度为0则,返回空
    if len(short) == 0 { //边界条件 .
        return ""
    }
    fmt.Println("short", short)
    //因为我们只求前缀.将最短字符串比较即可.
    for i := 0; i < len(short); i++ { //循环最短字符串. 然后与数组里每一个字符串按挨个字符进行比较.只要遇到不相等则截取最短字符串.
        for j := 0; j < l; j++ { //循环字符串数组.
            fmt.Printf("i:%d,j:%d, str;%s, s:%c, v:%c\n", i, j, strs[j], strs[j][i], short[i])
            if strs[j][i] != short[i] { //循环进行挨个字符进行比较.只要发现不相等的则截取返回.
                short = strs[j][:i] //只要不相等,则截取数组里的字符最短前缀.
                return short
            }
        }
    }
    return short
}

解法二: 水平扫描法

1. 处理边界条件
2. 默认从数组里获取一个元素做参照字符串.
3. 然后对数组进行遍历, 里面再进行不断循环判断参照字符串是不是数组某个元素的字集
4. 如果不是子集,则进行将参照字符串进行砍掉一个字符的尾巴. 直到是数组里某个字符串的子集.
5. 注意循环里的边界条件

//水平扫描法
func longestCommonPrefixV2(strs []string) string {
    l := len(strs)
    if l == 0 { //边界条件
        return ""
    }
    short := strs[0]                 //假设第一个字符是最小字符串.
    for i := 0; i < len(strs); i++ { //遍历整个数组
        for strings.Index(strs[i], short) != 0 {
            //循环处理, 只要minPrefix不是子集则继续循环.
            // 每次对minPrefix减小一个字符进行循环比较
            if len(strs[i]) == 0 { //边界条件, 如果数组里有空的元素,则直接返回为空
                return ""
            }
            short = short[0 : len(short)-1] //每次减小一个字符进行下一轮比较.
            fmt.Printf("str:%s, min:%s\n", strs[i], short)
        }
    }
    return short
}