27-附：字符串专题汇总.md

```Go
package main

import (
	"math"
)

// 1、 判断两个字符串是否互为变形词
func isDeformation(str1, str2 string) bool {
	if len(str1) == 0 || len(str2) == 0 || len(str1) != len(str2) {
		return false
	}

	chars1 := []byte(str1)
	chars2 := []byte(str2)

	// 字符词频统计表
	m := make([]int, 256)

	// 对第一个字符串中的字符进行词频统计
	for _, c := range chars1 {
		m[c]++
	}

	// 用第二个字符串的字符去消除词频
	for _, c := range chars2 {
		if m[c] == 0 {
			return false
		}
		m[c]--
	}

	return true
}

// 2、 移除字符串中连续出现k个0的子串
func removeKZeros(str string, k int) string {
	if len(str) == 0 || k < 1 {
		return str
	}

	chars := []byte(str)
	count := 0
	start := -1

	for i := 0; i < len(chars); i++ {
		if chars[i] == '0' {
			count++
			if start == -1 {
				start = i
			}
		} else {
			// 如果不等于'0'需要从start位置开始，去掉count个'0'字符
			if count == k {
				for ; count != 0; count++ {
					// ascii码空白字符的表示为十进制的0。chars[1] = 0 表示把1位置的字符，替换为空白符
					chars[start] = 0
					start++
				}
			}
			// 一轮剔除结束，count和start归位
			count = 0
			start = -1
		}
	}

	// 最后一轮，即如果字符串是以'0'字符结尾的。最后要单独结算一次
	if count == k {
		for ; count != 0; count-- {
			chars[start] = 0
			start++
		}
	}

	return string(chars)
}

// 3、判断字符数组中，是否所有的字符均出现一次
func isUnique(chars []byte) bool {
	if len(chars) == 0 {
		return true
	}

	m := make([]bool, 256)
	for i := 0; i < len(chars); i++ {
		if m[chars[i]] {
			return false
		}
		m[chars[i]] = true
	}

	return true
}

// 4、括号字符匹配问题：输入一个字符串，包含'(','[','{',')',']','}'几种括号，求是否是括号匹配的结果。
func isValid(s string) bool {
	if len(s) == 0 {
		return true
	}

	chars := []byte(s)
	stack := make([]byte, 0)

	for i := 0; i < len(chars); i++ {
		c := chars[i]
		// 遇到左括号，添加相应的右括号
		if c == '(' || c == '[' || c == '{' {
			if c == '(' {
				stack = append(stack, ')')
			}
			if c == '[' {
				stack = append(stack, ']')
			}
			if c == '{' {
				stack = append(stack, '}')
			}
		} else { // 遇到右括号，弹出栈，比对相等
			if len(stack) == 0 {
				return false
			}

			last := stack[len(stack)-1]
			stack = stack[:len(stack)-1]

			if c != last {
				return false
			}
		}
	}

	// 遍历结束，栈刚好为空。满足匹配要求
	return len(stack) == 0
}

// 5、求一个字符串无重复最长子串
// 子串和子序列的区别，子串必须要连续，子序列不一定要连续。
// 遇到子串和子序列的问题，可以按照一种经典思路：
// 按照i位置结尾的情况下答案是什么？求所有可能的结尾即可，所有位置结尾的答案都求出，最大的就是我们的目标答案
// 时间复杂度O(N)，空间复杂度O(1)，由于申请的空间是固定长度256
func lengthOfLongestSubstring(s string) int {
	// base case 过滤无效参数
	if len(s) == 0 {
		return 0
	}

	chars := []byte(s)
	m := make([]int, 256)
	// 辅助数组。保存字符出现的位置，字符的范围为可显示字符0~127，扩展ascii字符128~255。0~255共256
	for i := 0; i < 256; i++ {
		//  默认所有的字符都没出现过
		m[i] = -1
	}

	// i位置往左推，推不动的位置第一个因素是再次遇到了i位置上的元素，第二个因素是i-1位置当初推了多远。
	// 这两个因素的限制，哪个限制位置离当前i位置近，就是当前字符i最远推到的位置，map[i]
	// 收集答案。len是收集全局的最大长度
	length := 0
	pre := -1 // i-1位置结尾的情况下，往左推，推不动的位置是谁。用来每次保存i之前一个位置的答案
	cur := 0

	for i := 0; i != len(chars); i++ {
		// i位置结尾的情况下，往左推，推不动的位置是谁
		// pre (i-1信息) 更新成 pre(i 结尾信息)
		// 上次推不动的，和当前字符上次出现的位置map[str[i]]的位置，取大的
		pre = int(math.Max(float64(pre), float64(m[chars[i]])))
		// 找到了当前推不动的位置，当前不重复子串的长度就是i-pre
		cur = i - pre
		// 全局最大的子串长度，是否被更新，决定是否要收集
		length = int(math.Max(float64(length), float64(cur)))
		// 更新当前字符出现的位置是当前位置
		m[chars[i]] = i
	}

	return length
}

// 6、最长回文子串问题。
// 该解法是扩散法。时间复杂度为O(N * N)。(最优解是马拉车算法，可以优化该题到O(N)，不掌握)
func longestPalindrome2(s string) string {
	if len(s) == 0 {
		return s
	}

	// 全局最大回文长度
	res := 1
	// 全局最大回文长度对应的左位置
	ll := 0
	// 全局最大回文长度对应的右位置
	rr := 0

	for i := 0; i < len(s); i++ {
		// 以i为下标的奇数情况，是否有更大的len来更新res
		l := i - 1
		r := i + 1
		// l和r都在合法范围。且l和r位置字符相等，可以继续扩散
		for l >= 0 && r < len(s) && s[l] == s[r] {
			length := r - l + 1
			// 更新最长回文串的长度
			if length > res {
				res = length
				ll = l
				rr = r
			}
			// 扩散
			l--
			r++
		}

		// 以i为下标偶数的情况。是否有更大的len来更新全局res
		l = i
		r = i + 1
		// l和r都在合法范围。且l和r位置字符相等，可以继续扩散
		for l >= 0 && r < len(s) && s[l] == s[r] {
			length := r - l + 1
			// 更新最长回文串的长度
			if length > res {
				res = length
				ll = l
				rr = r
			}
			// 扩散
			l--
			r++
		}
	}
	return s[ll : rr+1] // 等价于s.subString(2, 7)都是左闭右开
}

// 7、字符串最长公共前缀问题
func longestCommonPrefix(strs []string) string {
	if len(strs) == 0 {
		return ""
	}

	// 拿出第一个字符串。当成初始值
	chars := []byte(strs[0])
	// 所有字符串都匹配的最大长度，等同于每个字符串和初始字符串匹配的全局最小长度
	min := math.MaxInt

	for _, str := range strs {
		tmp := []byte(str)
		index := 0

		for index < len(tmp) && index < len(chars) {
			if chars[index] != tmp[index] {
				break
			}
			index++
		}

		// 更新min
		min = int(math.Min(float64(index), float64(min)))
		// 如果有任意一个字符串和初始串不匹配，直接返回""
		if min == 0 {
			return ""
		}
	}
	return strs[0][0:min] // strs[0].substring(0, min);
}
```