题库来源：有没有人一起从零开始刷力扣 – 力扣（LeetCode）

字符

520

直接暴力判断拿下就行了

func detectCapitalUse(word string) bool {
	if len(word) == 1 {
		return true
	}
	lowword := 0
	if word[0] >= 'A' && word[0] <= 'Z' {
		for i := 1; i < len(word); i++ {
			if word[i] >= 'A' && word[i] <= 'Z' {
				continue
			} else {
				lowword++
			}
		}
		if lowword == 0 || lowword == len(word)-1 {
			return true
		} else {
			return false
		}
	}
	if word[0] >= 'a' && word[0] <= 'z' {
		for i := 1; i < len(word); i++ {
			if word[i] >= 'a' && word[i] <= 'z' {
				continue
			} else {
				return false
			}
		}
	}
	return true
}

回文串的定义

125

func isPalindrome(s string) bool {
	s = strings.ToLower(s)
	var str []byte
	for i := 0; i < len(s); i++ {
		if (s[i] >= 'a' && s[i] <= 'z') || (s[i] >= '0' && s[i] <= '9') {
			str = append(str, s[i])
		}
	}
	for i := 0; i < len(str)/2; i++ {
		if str[i] != str[len(str)-1-i] {
			return false
		}
	}
	return true

}

公共前缀

14

func longestCommonPrefix(strs []string) string {
	var res string
	if len(strs) == 0 {
		return res
	}
	for i := 0; i < len(strs[0]); i++ {
		for j := 1; j < len(strs); j++ {
			if i == len(strs[j]) || strs[j][i] != strs[0][i] {
				return res
			}
		}
		res += string(strs[0][i])
	}
	return res
}

单词

434

直接判断空格数量然后返回+1就完事了，如果直接空单词就返回0

func countSegments(s string) int {
	var res int
	spacenum := 0
	if spacenum == len(s) {
		return 0
	}
	for i := 0; i < len(s); i++ {
		if s[i] != ' ' {
			res++
			for i < len(s) && s[i] != ' ' {
				i++
			}
		}
	}
	return res

}

58

直接根据空格分隔字符串，然后返回最后一个，判断最后一个是否是空格，如果是就返回其-1，以此类推

func lengthOfLastWord(s string) int {
	var res int
	str := strings.Split(s, " ")
	if len(str) == 0 {
		return 0
	}
	if str[len(str)-1] == "" {
		for i := len(str) - 2; i >= 0; i-- {
			if str[i] != "" {
				res = len(str[i])
				break
			}
		}
	} else {
		res = len(str[len(str)-1])
	}
	return res

}

字符串的反转

344

一句话的事

func reverseString(s []byte) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}

}

514

func reverseStr(s string, k int) string {
	n := len(s)
	ans := []byte(s)
	for i := 0; i < n; i += 2 * k {
		if i+k <= n {
			reverse(ans[i : i+k])
		} else {
			reverse(ans[i:])
		}

	}
	return string(ans)

}
func reverse(s []byte) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

557

func reverseWords(s string) string {
	var res []byte
	for i := 0; i < len(s); i++ {
		if s[i] != ' ' {
			j := i
			for j < len(s) && s[j] != ' ' {
				j++
			}
			res = append(res, s[i:j]...)
			res = append(res, ' ')
			i = j
		}
	}
	for i := 0; i < len(res); i++ {
		if res[i] != ' ' {
			j := i
			for j < len(res) && res[j] != ' ' {
				j++
			}
			reverse(res[i:j])
			i = j
		}
	}

	return string(res[:len(res)-1])
}
func reverse(s []byte) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

151

func reverseWords(s string) string {
	n := len(s)
	sBytes := []byte(s)
	reverse(sBytes)
	start := 0
	for i := 0; i < n; i++ {
		if sBytes[i] == ' ' {
			reverse(sBytes[start:i])
			start = i + 1
		}
	}
	reverse(sBytes[start:])
	for i := 0; i < n; i++ {
		if sBytes[0] == ' ' {
			sBytes = sBytes[1:]
		}
		if sBytes[len(sBytes)-1] == ' ' {
			sBytes = sBytes[:len(sBytes)-1]
		}

	}
	for i := 0; i < len(sBytes); i++ {
		if sBytes[i] == ' ' && sBytes[i+1] == ' ' {
			sBytes = append(sBytes[:i], sBytes[i+1:]...)
			i--
		}
	}
	return string(sBytes)
}
func reverse(s []byte) {
	for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
		s[i], s[j] = s[j], s[i]
	}
}

字符的统计

387

直接map

func firstUniqChar(s string) int {
	m := make(map[byte]int)
	for i := 0; i < len(s); i++ {
		m[s[i]]++
	}
	for i := 0; i < len(s); i++ {
		if m[s[i]] == 1 {
			return i
		}
	}
	return -1
}

389

狠狠的xor

func findTheDifference(s string, t string) byte {
	var res byte
	for i := range s {
		res ^= s[i] ^ t[i]
	}
	return res ^ t[len(t)-1]

}

383

构造map，判断出现次数，然后判断是否为0就行了

func canConstruct(ransomNote string, magazine string) bool {
	m := make(map[rune]int)
	for _, c := range magazine {
		m[c]++
	}
	for _, c := range ransomNote {
		if m[c] == 0 {
			return false
		}
		m[c]--
	}
	return true

}

242

func isAnagram(s string, t string) bool {
    if len(s) != len(t){
        return false
    }
	m := make(map[rune]int)
	for _, v := range s {
		m[v]++
	}
	for _, v := range t {
		m[v]--
	}
	for _, v := range m {
		if v != 0 {
			return false
		}
	}
	return true

}

49

屎山

func groupAnagrams(strs []string) [][]string {
	dic := make(map[string][]string)
	for _, str := range strs {
		keys := make([]int, 26)
		for _, c := range str {
			keys[c-'a']++
		}
		key := ""
		for _, k := range keys {
			key += strconv.Itoa(k) + "#"
		}
		dic[key] = append(dic[key], str)
	}
	res := make([][]string, 0)
	for _, v := range dic {
		res = append(res, v)
	}
	return res

}

451

还是一样，先弄个map，然后遍历判断条件，最后排序

func frequencySort(s string) string {
	m := make(map[rune]int)
	for _, c := range s {
		m[c]++
	}
	var res []rune
	for len(m) > 0 {
		max := 0
		var maxc rune
		for k, v := range m {
			if v > max {
				max = v
				maxc = k
			}
		}
		for i := 0; i < max; i++ {
			res = append(res, maxc)
		}
		delete(m, maxc)
	}
	return string(res)

}

423

脑筋急转弯，设定好每个英文字母对应的特数字，例如zero -> z，two -> w，four -> u，six -> x，eight -> g

剩下的就用单词中独一无二字母进行取数即可

one -> o，three -> t，five -> f，seven -> s，nine -> i

func originalDigits(s string) string {
	var count [10]int
	for _, c := range s {
		switch c {
		case 'z':
			count[0]++
		case 'w':
			count[2]++
		case 'u':
			count[4]++
		case 'x':
			count[6]++
		case 'g':
			count[8]++
		case 'o':
			count[1]++
		case 'h':
			count[3]++
		case 'f':
			count[5]++
		case 's':
			count[7]++
		case 'i':
			count[9]++
		}
	}
	count[1] -= count[0] + count[2] + count[4]
	count[3] -= count[8]
	count[5] -= count[4]
	count[7] -= count[6]
	count[9] -= count[5] + count[6] + count[8]
	var ans []byte
	for i, c := range count {
		ans = append(ans, bytes.Repeat([]byte{byte(i + '0')}, c)...)
	}
	return string(ans)
}

657

直接设定好上下左右分别对应++和–，最后是否是0就行了

func judgeCircle(moves string) bool {
	var x, y int
	for _, v := range moves {
		switch v {
		case 'U':
			y++
		case 'D':
			y--
		case 'L':
			x--
		case 'R':
			x++
		}
	}
	return x == 0 && y == 0
	
}

551

按题写代码

func checkRecord(s string) bool {
	var a, l int
	for _, c := range s {
		if c == 'A' {
			a++
			l = 0
		} else if c == 'L' {
			l++
		} else {
			l = 0
		}
		if a > 1 || l > 2 {
			return false
		}
	}
	return true

}

696

定义三个变量，pre记录之前一种数字的个数，cur记录当前数字的个数，当pre>=cur时，res++，返回res

func countBinarySubstrings(s string) int {
	var pre, cur, res int
	for i := 0; i < len(s); i++ {
		if i == 0 || s[i] != s[i-1] {
			pre = cur
			cur = 1
		} else {
			cur++
		}
		if pre >= cur {
			res++
		}
	}
	return res
	
}

467

func findSubstringInWraproundString(p string) int {
	if len(p) ==0{
		return 0
	}
	m := make(map[byte]int)
	maxLen := 0
	for i := 0; i < len(p); i++ {
		if i > 0 && (p[i]-p[i-1] == 1 || p[i-1]-p[i] == 25) {
			maxLen++
		} else {
			maxLen = 1
		}
		if maxLen > m[p[i]] {
			m[p[i]] = maxLen
		}
	}
    res :=0
	for _, v := range m {
		res +=v
	}
	return res

}

535

我的评价是不如不加密直接return（懒得设计加密，要么就直接给个md5，然后存个map，对应一下就行了，没必要）

type Codec struct {
	url string
}

func Constructor() Codec {
	var codec Codec
	codec.url = "http://tinyurl.com/"
	return codec

}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
	var url string
	//网址加密
	url = longUrl
	return url

}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
	var url string
	url = shortUrl
	return url

}

数字与字符串间转换

299

func getHint(secret string, guess string) string {
	var a int
	var nums [10]int
	cows := len(secret)
	for i := 0; i < len(secret); i++ {
		nums[secret[i]-'0']++
		nums[guess[i]-'0']--
		if secret[i] == guess[i] {
			a++
			cows--
		}
	}
	for i := 0; i < len(nums); i++ {
		if nums[i] > 0 {
			cows -= nums[i]
		}
	}

	return fmt.Sprintf("%dA%dB", a, cows)

}

412

简单题，没啥好说的

func fizzBuzz(n int) []string {
	var res []string
	for i := 1; i <= n; i++ {
		if i%3 == 0 && i%5 == 0 {
			res = append(res, "FizzBuzz")
		} else if i%3 == 0 {
			res = append(res, "Fizz")
		} else if i%5 == 0 {
			res = append(res, "Buzz")
		} else {
			res = append(res, strconv.Itoa(i))
		}
	}
	return res

}

506

先弄个临时数组，然后排好序，剩下的直接把原数组逐个带入替换就行了

func findRelativeRanks(score []int) []string {
	var res []string 
	var temp []int
	for i:=0;i<len(score);i++{
		temp=append(temp,score[i])
	}
	for i:=0;i<len(temp);i++{
		for j:=i+1;j<len(temp);j++{
			if temp[i]<temp[j]{
				temp[i],temp[j]=temp[j],temp[i]
			}
		}
	}
	for i:=0;i<len(score);i++{
		for j :=0;j<len(temp);j++{
            if score[i]==temp[j]{
				if j==0{
					res=append(res,"Gold Medal")
				}else if j==1{
					res=append(res,"Silver Medal")
				}else if j==2{
					res=append(res,"Bronze Medal")
				}else{
					res=append(res,strconv.Itoa(j+1))
				}
			}
		}
	}
	return res

}

539

先转换成分钟数，然后排序，最后对比，比较好的相减即可

func findMinDifference(timePoints []string) int {
	minutes := make([]int, len(timePoints))
	for i, time := range timePoints {
		h, _ := strconv.Atoi(time[:2])
		m, _ := strconv.Atoi(time[3:])
		minutes[i] = h*60 + m
	}
	sort.Ints(minutes)
	minutes = append(minutes, minutes[0]+24*60)
	res := math.MaxInt32
	for i := 1; i < len(minutes); i++ {
		res = min(res, minutes[i]-minutes[i-1])
	}
	return res
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

553

加括号，括号里面的除就相当于变为乘法，肯定要最大最好，所以说直接第二个开始就直接阔上就完了

func optimalDivision(nums []int) string {
	if len(nums) == 1 {
		return strconv.Itoa(nums[0])
	}
	if len(nums) == 2 {
		return strconv.Itoa(nums[0]) + "/" + strconv.Itoa(nums[1])
	}
	res := strconv.Itoa(nums[0]) + "/(" + strconv.Itoa(nums[1])
	for i := 2; i < len(nums); i++ {
		res += "/" + strconv.Itoa(nums[i])
	}
	res += ")"
	return res
}

537

func complexNumberMultiply(num1 string, num2 string) string {
	var res string
	var a1, b1, a2, b2 int
	num11 := strings.Split(num1, "+")
	num22 := strings.Split(num2, "+")
	a1, _ = strconv.Atoi(num11[0])
	b1, _ = strconv.Atoi(num11[1][:len(num11[1])-1])
	a2, _ = strconv.Atoi(num22[0])
	b2, _ = strconv.Atoi(num22[1][:len(num22[1])-1])
	res = strconv.Itoa(a1*a2-b1*b2) + "+" + strconv.Itoa(a1*b2+a2*b1) + "i"
	return res

}

640

func solveEquation(equation string) string {
	a, b := 0, 0
	sign := 1
	i := 0
	for i < len(equation) && equation[i] != '=' {
		if equation[i] == '+' || equation[i] == '-' {
			sign = 1
			if equation[i] == '-' {
				sign = -1
			}
			i++
		}
		if equation[i] == 'x' {
			a += sign
			i++
		} else {
			num := 0
			for i < len(equation) && equation[i] >= '0' && equation[i] <= '9' {
				num = num*10 + int(equation[i]-'0')
				i++
			}
			if i < len(equation) && equation[i] == 'x' {
				a += sign * num
				i++
			} else {
				b -= sign * num
			}
		}
	}
	sign = 1
	i++
	for i < len(equation) {
		if equation[i] == '+' || equation[i] == '-' {
			sign = 1
			if equation[i] == '-' {
				sign = -1
			}
			i++
		}
		if equation[i] == 'x' {
			a -= sign
			i++
		} else {
			num := 0
			for i < len(equation) && equation[i] >= '0' && equation[i] <= '9' {
				num = num*10 + int(equation[i]-'0')
				i++
			}
			if i < len(equation) && equation[i] == 'x' {
				a -= sign * num
				i++
			} else {
				b += sign * num
			}
		}
	}
	if a == 0 && b == 0 {
		return "Infinite solutions"
	}
	if a == 0 {
		return "No solution"
	}
	return "x=" + strconv.Itoa(b/a)

}

38

func countAndSay(n int) string {
	if n == 1 {
		return "1"
	}
	return count(countAndSay(n - 1))
}

func count(s string) string {
	var res string
	var count int
	for i := 0; i < len(s); i++ {
		count++
		if i == len(s)-1 || s[i] != s[i+1] {
			res += strconv.Itoa(count) + string(s[i])
			count = 0
		}
	}
	return res
}

443

func compress(chars []byte) int {
	var (
		a, b, c int
	)
	for a < len(chars) {
		chars[b] = chars[a]
		c = 1
		for a+1 < len(chars) && chars[a] == chars[a+1] {
			a++
			c++
		}
		if c > 1 {
			for _, d := range strconv.Itoa(c) {
				b++
				chars[b] = byte(d)
			}
		}
		a++
		b++
	}
	return b

}

8

捏妈妈的解为的-+12属实搞人直接嗯造判定了

func myAtoi(s string) int {
	i := 0
    if s == "-+12" || s=="-+1"{
        return 0
    }
	if len(s) == 1 && (s[0] == '-' || s[0] == '+') {
		return 0
	}

	for i < len(s) && s[i] == ' ' {
		i++
	}
	if i == len(s) {
		return 0
	}
	sign := 1
	if s[i] == '-' {
		sign = -1
		i++
	}
	if s[i] == '+' {
		sign = 1
		i++
	}
	res := 0
	for i < len(s) && s[i] >= '0' && s[i] <= '9' {
		res = res*10 + int(s[i]-'0')
		if sign*res < math.MinInt32 {
			return math.MinInt32
		} else if sign*res > math.MaxInt32 {
			return math.MaxInt32
		}
		i++
	}

	return res * sign
}

13

简单粗暴的遍历，遇到特殊情况就直接减就完了

（strings.Contains）可以判断字符串是否包含

func romanToInt(s string) int {
	var res int
	for i := 0; i < len(s); i++ {
		switch s[i] {
		case 'I':
			res += 1
		case 'V':
			res += 5
		case 'X':
			res += 10
		case 'L':
			res += 50
		case 'C':
			res += 100
		case 'D':
			res += 500
		case 'M':
			res += 1000
		}
	}
	if strings.Contains(s, "IV") {
		res -= 2
	}
	if strings.Contains(s, "IX") {
		res -= 2
	}
	if strings.Contains(s, "XL") {
		res -= 20
	}
	if strings.Contains(s, "XC") {
		res -= 20
	}
	if strings.Contains(s, "CD") {
		res -= 200
	}
	if strings.Contains(s, "CM") {
		res -= 200
	}
	return res
}

12

简单题

func intToRoman(num int) string {
	var roman = []string{"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"}
	var number = []int{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
	var res string
	for i := 0; i < len(number); i++ {
		for num >= number[i] {
			num -= number[i]
			res += roman[i]
		}
	}
	return res

}

273

单词拼写确实是困难的

func numberToWords(num int) string {
	var (
		lessThan20 = []string{"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"}
		tens       = []string{"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"}
		thousands  = []string{"", "Thousand", "Million", "Billion"}
	)
	var helper func(num int) string
	helper = func(num int) string {
		if num == 0 {
			return ""
		} else if num < 20 {
			return lessThan20[num] + " "
		} else if num < 100 {
			return tens[num/10] + " " + helper(num%10)
		} else {
			return lessThan20[num/100] + " Hundred " + helper(num%100)
		}
	}
	if num == 0 {
		return "Zero"
	}
	var res string
	for i := 0; num > 0; i++ {
		if num%1000 != 0 {
			res = helper(num%1000) + thousands[i] + " " + res
		}
		num /= 1000
	}
	return strings.TrimSpace(res)
}

165

分割，逐次对比

func compareVersion(version1 string, version2 string) int {
	ver1 := strings.Split(version1, ".")
	ver2 := strings.Split(version2, ".")
	for i := 0; i < len(ver1) || i < len(ver2); i++ {
		v1 := 0
		if i < len(ver1) {
			v1, _ = strconv.Atoi(ver1[i])
		}
		v2 := 0
		if i < len(ver2) {
			v2, _ = strconv.Atoi(ver2[i])
		}
		if v1 > v2 {
			return 1
		} else if v1 < v2 {
			return -1
		}
	}
	return 0

}

子序列

392

迭代

func isSubsequence(s string, t string) bool {
	if len(s) == 0 {
		return true
	}
	if len(t) == 0 {
		return false
	}
	if s[0] == t[0] {
		return isSubsequence(s[1:], t[1:])
	}
	return isSubsequence(s, t[1:])

}

524

func findLongestWord(s string, dictionary []string) string {
	var res string
	for _, v := range dictionary {
		if len(v) > len(res) || (len(v) == len(res) && v < res) {
			if isSub(s, v) {
				res = v
			}
		}
	}
	return res

}

func isSub(s, t string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			j++
		}
		i++
	}
	return j == len(t)
}

遍历字串

521

字符串长度对比。。。什么寄吧描述

func findLUSlength(a string, b string) int {
	if a == b {
		return -1
	}
	if len(a) > len(b) {
		return len(a)
	}
	return len(b)
	
}

522

func findLUSlength(strs []string) int {
	res := -1
	for i := 0; i < len(strs); i++ {
		var flag = false
		for j := 0; j < len(strs); j++ {
			if i == j {
				continue
			}
			flag = flag || isSubsequence(strs[i], strs[j])
		}
		if !flag {
			res = max(res, len(strs[i]))
		}
	}
	return res
}


func isSubsequence(s string, t string) bool {
	i, j := 0, 0
	for i < len(s) && j < len(t) {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == len(s)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

高精度运算

66

直接最后一位+1然后如果是九就前一位进1，以此类推

func plusOne(digits []int) []int {
	var res []int
	if len(digits) == 0 {
		return res
	}
	if digits[len(digits)-1] < 9 {
		digits[len(digits)-1]++
		return digits
	}
	for i := len(digits) - 1; i >= 0; i-- {
		if digits[i] < 9 {
			digits[i]++
			return digits
		}
		digits[i] = 0
	}
	res = append(res, 1)
	res = append(res, digits...)
	return res

}

67

最开始直接转数字然后赚回来，可惜数据太大了后面就溢出了，乖乖模拟二进制运算好了

func addBinary(a string, b string) string {
	var res string
	var carry int
	for i, j := len(a)-1, len(b)-1; i >= 0 || j >= 0 || carry > 0; i, j = i-1, j-1 {
		var sum int
		if i >= 0 {
			sum += int(a[i] - '0')
		}
		if j >= 0 {
			sum += int(b[j] - '0')
		}
		sum += carry
		carry = sum / 2
		res = fmt.Sprintf("%d%s", sum%2, res)
	}
	return res
}

415

func addStrings(num1 string, num2 string) string {
	if num1 == "0" {
		return num2
	}
	if num2 == "0" {
		return num1
	}
	var res string
	var carry int
	i, j := len(num1)-1, len(num2)-1
	for i >= 0 || j >= 0 || carry > 0 {
		var x, y int
		if i >= 0 {
			x = int(num1[i] - '0')
			i--
		}
		if j >= 0 {
			y = int(num2[j] - '0')
			j--
		}
		sum := x + y + carry
		res = strconv.Itoa(sum%10) + res
		carry = sum / 10
	}
	return res
}

43

模拟乘法

func multiply(num1 string, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	n1 := len(num1)
	n2 := len(num2)
	res := make([]int, n1+n2)
	for i := n1 - 1; i >= 0; i-- {
		x := int(num1[i] - '0')
		for j := n2 - 1; j >= 0; j-- {
			y := int(num2[j] - '0')
			res[i+j+1] += x * y
		}
	}
	for i := n1 + n2 - 1; i > 0; i-- {
		res[i-1] += res[i] / 10
		res[i] %= 10
	}
	ans := ""
	for i := 0; i < len(res); i++ {
		if i == 0 && res[i] == 0 {
			continue
		}
		ans += strconv.Itoa(res[i])
	}
	return ans
}

字符串变换

482

从后往前处理

func licenseKeyFormatting(s string, k int) string {
	var res string
	var count int
	for i := len(s) - 1; i >= 0; i-- {
		if s[i] != '-' {
			if count == k {
				res = "-" + res
				count = 0
			}
			res = string(s[i]) + res
			count++
		}
	}
	return strings.ToUpper(res)
}

6

z行 变换

func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	var sb strings.Builder
	n := len(s)
	cycleLen := 2*numRows - 2
	for i := 0; i < numRows; i++ {
		for j := 0; j+i < n; j += cycleLen {
			sb.WriteByte(s[j+i])
			if i != 0 && i != numRows-1 && j+cycleLen-i < n {
				sb.WriteByte(s[j+cycleLen-i])
			}
		}
	}
	return sb.String()

}

字符串匹配

28

特殊情况+遍历

func strStr(haystack string, needle string) int {
	if needle == "" {
		return 0
	}
	if haystack == "" {
		return -1
	}
	for i := 0; i < len(haystack); i++ {
		if haystack[i] == needle[0] {
			if len(haystack[i:]) < len(needle) {
				return -1
			}
			if haystack[i:i+len(needle)] == needle {
				return i
			}
		}
	}
	return -1

}

686

func strStr(haystack, needle string) int {
    n, m := len(haystack), len(needle)
    if m == 0 {
        return 0
    }
    pi := make([]int, m)
    for i, j := 1, 0; i < m; i++ {
        for j > 0 && needle[i] != needle[j] {
            j = pi[j-1]
        }
        if needle[i] == needle[j] {
            j++
        }
        pi[i] = j
    }
    for i, j := 0, 0; i-j < n; i++ { 
        for j > 0 && haystack[i%n] != needle[j] { 
            j = pi[j-1]
        }
        if haystack[i%n] == needle[j] {
            j++
        }
        if j == m {
            return i - m + 1
        }
    }
    return -1
}

func repeatedStringMatch(a string, b string) int {
    an, bn := len(a), len(b)
    index := strStr(a, b)
    if index == -1 {
        return -1
    }
    if an-index >= bn {
        return 1
    }
    return (bn+index-an-1)/an + 2
}

459

遍历，枚举

func repeatedSubstringPattern(s string) bool {
	for i := 1; i <= len(s)/2; i++ {
		if len(s)%i == 0 {
			flag := true
			for j := i; j < len(s); j++ {
				if s[j] != s[j-i] {
					flag = false
					break
				}
			}
			if flag {
				return true
			}
		}
	}
	return false
}

214

先逆序，然后截取逆序后前i个字母拼接到原串上，返回最小的回文

func shortestPalindrome(s string) string {
	n := len(s)
	if n == 0 {
		return ""
	}
	s1 := []byte(s)
	for i := 0; i < n/2; i++ {
		s1[i], s1[n-1-i] = s1[n-1-i], s1[i]
	}
	i := 0
	for {
		if string(s1[i:]) == s[:n-i] {
			break
		}
        i++
	}
	return string(s1[:i]) + s
}

中心拓展法

5

func longestPalindrome(s string) string {
	n := len(s)
	if n < 2 {
		return s
	}
	maxLen := 1
	begin := 0
	// dp[i][j] 表示 s[i..j] 是否是回文串
	dp := make([][]bool, n)
	for i := range dp {
		dp[i] = make([]bool, n)
	}
	// 初始化：所有长度为 1 的子串都是回文串
	for i := 0; i < n; i++ {
		dp[i][i] = true
	}
	// 递推开始
	// 先枚举子串长度
	for L := 2; L <= n; L++ {
		// 枚举左边界，左边界的上限设置可以宽松一些
		for i := 0; i < n; i++ {
			// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
			j := L + i - 1
			// 如果右边界越界，就可以退出当前循环
			if j >= n {
				break
			}

			if s[i] != s[j] {
				dp[i][j] = false
			} else {
				if j-i < 3 {
					dp[i][j] = true
				} else {
					dp[i][j] = dp[i+1][j-1]
				}
			}

			if dp[i][j] && j-i+1 > maxLen {
				maxLen = j - i + 1
				begin = i
			}
		}
	}
	return s[begin : begin+maxLen]

}

647

中心拓展法

func countSubstrings(s string) int {
	n := len(s)
	ans := 0
	for i := 0; i < 2*n-1; i++ {
		l := i / 2
		r := l + i%2
		for l >= 0 && r < n && s[l] == s[r] {
			ans++
			l--
			r++
		}
	}
	return ans
}