leetcode_字符串合集

Golang字符串注意点⚠️

  1. 对字符串 range的时候,v并不是byte类型而是rune(底层为int32

    s := "hello world"
    for _, v := range s {
        fmt.Printf("%c, %T", v, v)
    }
    
  2. 字符串直接取某一位,比s[0],类型为byte(底层为uint8

    s := "hello world"
    for i := 0; i < len(s); i++ {
        fmt.Printf("%c, %T", s[i], s[i])
    }
    

    详细原理,见Go语言字符类型(byte和rune)

面试题 01.09. 字符串轮转

题目

字符串轮转。给定两个字符串s1和s2,请编写代码检查s2是否为s1旋转而成(比如,waterbottle是erbottlewat旋转后的字符串)。

示例1:

 输入:s1 = "waterbottle", s2 = "erbottlewat"
 输出:True

示例2:

 输入:s1 = "aa", "aba"
 输出:False

提示:

字符串长度在[0, 100000]范围内。 说明:

你能只调用一次检查子串的方法吗?

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/string-rotation-lcci 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

翻转之后的S2,拼接起来肯定是首位相连的,判断是否包含S1

解答

func isFlipedString(s1 string, s2 string) bool {
    if len(s1) != len(s2) {
        return false
    }

    return strings.Contains(s2+s2, s1)
}

自己实现Contains,用KMP算法

func getNext(s string) []int {
    next := make([]int,len(s))
    next[0] = -1
    i, j := 0,-1
    for i< len(s)-1 {
        if j==-1 || s[i]==s[j] {
            i++
            j++
            next[i] = j
        } else {
            j = next[j]
        }
    }
    return next
}
func KMPSearch(target string,text string) int {
    i, j := 0, 0
    next := getNext(target)
    for ; j< len(text);  {
        if i==len(target)-1 && target[i]==text[j] {
            return j-i
        }
        if j==-1 || target[i]==text[j] {
            i++
            j++
        } else {
            i = next[i]
        }
    }
    return -1
}

415. 字符串相加

题目

给定两个字符串形式的非负整数 num1 和num2 ,计算它们的和。

注意:

num1 和num2 的长度都小于 5100. num1 和num2 都只包含数字 0-9. num1 和num2 都不包含任何前导零。 你不能使用任何內建 BigInteger 库, 也不能直接将输入的字符串转换为整数形式。 通过次数27,747提交次数55,789

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/add-strings 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

就是大数加法问题,每一位相加,保留个位,十位数进位(如有)

func addStrings(num1 string, num2 string) string {
    i, j := len(num1)-1, len(num2)-1
    
    var t byte = 0 // 每一位相加结果
    var ret []byte // 结果
    
    for i >=0 || j >= 0 || t != 0 {
        if i >= 0 {
            // '9' - '0' = 9
            t += num1[i]-'0'
            i--
        }
        
        if j >= 0 {
            t += num2[j]-'0'
            j--
        }
        
        // 18%10 + '0' = 8
        ret = append(ret, t%10+'0')
        t /= 10 // 18 / 10 = 1
    }
    
    l := len(ret)-1
    for i:=0; i <= l; i++ {
        ret[i], ret[n] = ret[n], ret[i]
        l--
    }
    return string(ret)
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.0%的用户
// 内存消耗 :2.5 MB, 在所有 Go 提交中击败了80.49%的用户

187. 重复的DNA序列

题目

所有 DNA 都由一系列缩写为 A,C,G 和 T 的核苷酸组成,例如:“ACGAATTCCG”。在研究 DNA 时,识别 DNA 中的重复序列有时会对研究非常有帮助。

编写一个函数来查找 DNA 分子中所有出现超过一次的 10 个字母长的序列(子串)。

示例:

输入:s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
输出:["AAAAACCCCC", "CCCCCAAAAA"]

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/repeated-dna-sequences 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

题目意思是两次或以上的重复字串

窗口往前滑动窗口,用map计数,大于2时放入结果

func findRepeatedDnaSequences(s string) []string {
    if len(s) <= 10 {
        return []string{}
    }

    // 辅助map和窗口|最多有 len(s)-10+1 种情况
    sub := make(map[string]int, len(s)-9)
    // 11: 0-10/1-11 
    for i := 0; i < len(s)-9; i++ {
        sub[s[i:i+10]]++
    }

    ret := []string{}
    for k, v := range sub {
        if v > 1 {
            ret = append(ret, k)  
        }
    }
    return ret
}
// 执行用时 :16 ms, 在所有 Go 提交中击败了91.38%的用户
// 内存消耗 :7.2 MB, 在所有 Go 提交中击败了79.17%的用户

1209. 删除字符串中的所有相邻重复项 II

题目

给你一个字符串 s,「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母,并删除它们,使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作,直到无法继续为止。

在执行完所有删除操作后,返回最终得到的字符串。

本题答案保证唯一。

示例 1:

输入s = "abcd", k = 2
输出"abcd"
解释没有要删除的内容

示例 2:

输入s = "deeedbbcccbdaa", k = 3
输出"aa"
解释 
先删除 "eee"  "ccc"得到 "ddbbbdaa"
再删除 "bbb"得到 "dddaa"
最后删除 "ddd"得到 "aa"

示例 3:

输入s = "pbbcggttciiippooaais", k = 2
输出"ps"

提示:

1 <= s.length <= 10^5 2 <= k <= 10^4 s 中只含有小写英文字母。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string-ii 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

栈节点分别存储 字符值val 和 字符数量num

遍历目标字符串s

  • 栈空 或 栈顶.val != s[i] 入栈,否则 栈顶.num++
  • 栈顶.num = k 时 出栈

最后栈中的元素拼起来就是结果字符串

//  删      pbbcggttciiippooaais 2
//  bb      pcggttciiippooaais
//  gg      pcttciiippooaais
//  tt      pcciiippooaais
//  cc      piiippooaais
//  ii      pippooaais
//  pp      piooaais
//  oo      piaais
//  aa      piis
//  ii      ps

type node struct {
    val rune
    num int
}

func removeDuplicates(s string, k int) string {
    var stk []node
    for _, v := range s {
        if len(stk)==0 || stk[len(stk)-1].val != v {
            stk = append(stk, &node{
                val: v,
                num: 1,
            })
        } else {
            stk[len(stk)-1].num++
        }

        for len(stk) > 0 {
            // 重复元素,出栈
            if stk[len(stk)-1].num == k {
                stk = stk[:len(stk)-1]
            } else {
                break
            }
        }
    }

    ret := make([]rune, 0, len(stk))
    for _, v := range stk {
        for v.num > 0 {
            ret = append(ret, v.val)
            v.num--
        }
    }
    return string(ret)
}
// 执行用时 :0 ms, 在所有 Go 提交中击败了100.00%的用户
// 内存消耗 :4.5 MB, 在所有 Go 提交中击败了100.00%的用户

14. 最长公共前缀

题目

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “"。

示例 1:

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

示例 2:

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

说明:

所有输入只包含小写字母 a-z 。

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/longest-common-prefix 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解答

先找出最短的字符串st(结果肯定是以这个为基准)

再用指针对 每一个字符串的第 k 位和 st的第k位进行对比,不同的时候就return

func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}
	// 先找到最短的
	min := math.MaxInt32
	var st string
	for _, v := range strs {
		if len(v) < min {
			min = len(v)
			st = v
		}
	}
	if len(st) == 0 {
		return ""
	}

	for k := range st {
		for j := 0; j < len(strs); j++ {
			if strs[j][k] != st[k] {
				return st[:k]
			}
		}
	}
	return st
}

459. 重复的子字符串

题目

Difficulty: 简单

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母,并且长度不超过10000。

示例 1:

输入: "abab"

输出: True

解释: 可由子字符串 "ab" 重复两次构成。

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

解释: 可由子字符串 "abc" 重复四次构成。 (或者子字符串 "abcabc" 重复两次构成。)

Solution 1

Language: Go

模拟: - 创建临时字符串tmp记录对比串,往主串前滑动。 - 对比成功就往前,否则把s[i]接到tmp后面 - 结果:“abaababaab” 不通过 - 原因:需要回溯,而不是不匹配就继续增加

func repeatedSubstringPattern(s string) bool {
	if len(s) < 2 {
		return false
	}

	tmp := string(s[0])
	i := 1

	for i < len(s) {
		if len(tmp)+i < len(s) {
			if tmp != s[i:len(tmp)+i] {
				i++
				tmp = s[:i]
			} else {
				i += len(tmp)
			}
		}
		if len(tmp)+i == len(s) {
			if s[i:] == tmp {
				return true
			} else {
				return false
			}
		}
		if len(tmp)+i > len(s) {
			return false
		}
	}
	return true
}
// 执行用时 :4 ms, 在所有 Go 提交中击败了96.64%的用户
// 内存消耗 :6 MB, 在所有 Go 提交中击败了100.00%的用户

Solution 2

思路:新建ss=s+s,把ss的首元素和尾元素去掉,剩下的部分如果还含有s,则返回true。

假设ss是由s重复N次而成, 则 s+s 则有子串s重复2N次,现在ss=Ns, S+S=2Ns 因此s在(s+s)[1:-1]中必出现一次以上

func repeatedSubstringPattern(s string) bool {
	return strings.Contains((s+s)[1:2*len(s)-1], s)
}

383. 赎金信

Difficulty: 简单

给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串,判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成,返回 true ;否则返回 false

(题目说明:为了不暴露赎金信字迹,要从杂志上搜索各个需要的字母,组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)

注意:

你可以假设两个字符串均只含有小写字母。

canConstruct("a", "b") -> false
canConstruct("aa", "ab") -> false
canConstruct("aa", "aab") -> true

Solution

创建字典,遍历magazine 记录 magazine 内字母的数目

遍历 ransomNote,每过一个字母就消耗字典内的一个计数。

计数 <1 或 不存在计数的时候返回false

Language: Go

func canConstruct(ransomNote string, magazine string) bool {
    if len(ransomNote) > len(magazine) {
        return false
    }
    
    dic := make(map[byte]int, len(magazine))
    for _, v := range magazine {
        dic[byte(v)]++ 
    }
    
    for _, v := range ransomNote {
        if v, ok := dic[byte(v)]; !ok || v < 1 {
            return false
        }
        dic[byte(v)]--
    }
    return true
}
// 执行用时 :12 ms, 在所有 Go 提交中击败了65.64%的用户
// 内存消耗 :6.4 MB, 在所有 Go 提交中击败了50.00%的用户

分享: