leetcode_字符串合集

November 7, 2019 5 minutes read

面试 • 算法 • 数据结构

Golang字符串注意点⚠️

对字符串 range的时候，v并不是byte类型而是rune（底层为int32）

s := "hello world"
for _, v := range s {
    fmt.Printf("%c, %T", v, v)
}

字符串直接取某一位，比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%的用户