【Golang语言】LeetCode 1002. Find Common Characters

努力的C · · 127 次点击 · · 开始浏览    

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

给定仅有小写字母组成的字符串数组 A,返回列表中的每个字符串中都显示的全部字符(包括重复字符)组成的列表。例如,如果一个字符在每个字符串中出现 3 次,但不是 4 次,则需要在最终答案中包含该字符 3 次。
你可以按任意顺序返回答案。
https://leetcode-cn.com/problems/find-common-characters

Input: ["bella","label","roller"]
Output: ["e","l","l"]
Input: ["cool","lock","cook"]
Output: ["c","o"]

题意:找出所有字符串中都出现过的字符,其实就是求各个字符串的交集,可以按任意顺序返回。
思路一:求每次字符串中的字符出现次数,每次两两字符串比较,26个字符取最小次数的则为两字符串的交集,比如
bella b->1 e->1 l->2 a->1
label b->1 e->1 l->2 a->1 所以这俩字符串的交集就是a b e l l
然后继续往下遍历即可。
用value-'a' 表示26个字母 最后再 value+'a' 转回来


func commonChars(A []string) []string {
    result := make([]int, 26)
    for _, value := range A[0] {
        result[value-'a']++
    }
    for i := 1; i < len(A); i++ {
        temp := make([]rune, 26)
        for _, value := range A[i] {
            temp[value-'a']++
        }
        for j := 0; j < 26; j++ {
            result[j] = int(math.Min(float64(temp[j]), float64(result[j])))
        }
    }

    ret := make([]string, 0)
    for i := 0; i < 26; i++ {
        if result[i] > 0 {
            times := result[i]
            j := 0
            for j < times {
                ret = append(ret, string(i+'a'))
                j++
            }
        }
    }

    return ret
}

思路二:其实也是差不多,也是直接两两比较,求交集,比较到最后的结果就是最后的结果。不过这里的求交集方法不太一样。 由于要考虑到重复出现的字符,所以需要采用一个数组来记录某个字符最近一次被找到的位置。如果再次遇到该字符,那么将会从该位置后面开始寻找。

func commonChars1002(A []string) []string {
    result := make([]string, 0)
    if len(A) == 1 {
        for _, rune := range A[0] {
            result = append(result, string(rune))
        }

        return result
    }
    common := commonStr(A[0], A[1])
    for i := 2; i < len(A); i++ {
        common = commonStr(A[i], common)
    }
    for _, rune := range common {
        result = append(result, string(rune))
    }
    return result
}
func commonStr(a string, b string) string {
    indexMap := [26]int{}
    result := make([]rune, 0)
    index := 0
    for _, rune := range a {
        beforeIndex := indexMap[rune-'a']
        index = strings.Index(b[beforeIndex:], string(rune))
        if index < len(b) && index >= 0 {
            result = append(result, rune)
            indexMap[rune-'a'] = index + beforeIndex + 1//截取后索引会从0开始,所以得加上之前的
        }
    }
    return string(result)
}

本文来自:51CTO博客

感谢作者:努力的C

查看原文:【Golang语言】LeetCode 1002. Find Common Characters

入群交流(和以上内容无关):Go中文网 QQ 交流群:798786647 或加微信入微信群:274768166 备注:入群;关注公众号:Go语言中文网

127 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传