字符串相关题目

字符串类相关题目

无重复字符的最长子串

https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

动态规划

已知以位置i-1结束的最长不重复串长为x, 若i处字符到其上一次出现的位置长为n

若 n > x, 则 以位置i结束的最长不重复串长为x+1

若 n <= x, 则 以位置i结束的最长不重复串长为n

验证IP地址

https://leetcode-cn.com/problems/validate-ip-address/

10进制字符串转int
n, err := strconv.ParseInt(s, 10, 32)

16进制字符串转int
n, err := strconv.ParseInt(s, 16, 32)

字母异位词分组

https://leetcode-cn.com/problems/group-anagrams/

字符串排序hash

func code(str string) string {
    s := []byte(str)
    sort.Slice(s, func(i, j int) bool { return s[i] < s[j] })
    sortedStr := string(s)
    return sortedStr
}

最小覆盖子串

https://leetcode-cn.com/problems/minimum-window-substring/

双指针法，不匹配时右移右指针，匹配时记录最短串，并右移左指针。

直到右指针达到末尾并且不匹配

找到字符串中所有字母异位词

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

使用双指针标记窗口，移动窗口依次比较。

使用26长数组代替字典。

进阶：

每次移入元素使得字典某字母数量匹配目标数量，使match++

每次移出元素使得字典某字母数量从匹配目标数量变为不匹配，使match–

当match等于元素种类时，记录当前窗口起始位置

字符串的排列

https://leetcode-cn.com/problems/permutations/

https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/

递归遍历

每层选择一个位置i

如果i到达序列尾部，则记录结果，否则

依次将i 与 j([i, len])位置处的数据交换。

如果位置j处的数据在此层之前([i, j-1])出现过，则跳过到下一位置

交换数据后进行递归，从位置i+1开始

递归结束后再次交换，恢复序列，并循环下一j。