基本概念

字串 是在字符串中，取出一块（连续的），如：pik, ach, kac等

子序列 指的是从字符串中，顺序取出字符，但是可以不连续：如：pau, kch, icu等

字符串比较

有效的字母异位词

242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

func isAnagram(s string, t string) bool {
   // 如果长度不一样，那么直接退出
   if len(s) != len(t) {
      return false
   }
   // 因为只有小写字母，所以我们可以只创建一个大小为26的数组
   a:=make([]int,26)
   for k:=range s{
      // 如果两个字符串相等的话，那么一个++一个--后，整个数组应该是为0的
      a[s[k]-'a'] ++
      a[t[k]-'a'] --
   }
   // 最后只要发现一个字符串不为0，那么我们就直接返回false
   for _,v:=range a{
      if v!=0 {
         return false
      }
   }
   return true
}

同构字符串

242. 有效的字母异位词 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

回文子串

647. 回文子串 - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

字符串理解

基本计算器II

227. 基本计算器 II - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这题目分为解析数字，然后进行计算。因为乘除的优先级更高，所以我们需要先想办法暂存数据然后进行计算，我们这里可以先不进行计算，先用right暂存，当遇到高优先级的比如*或者/这个时候我们就可以直接计算了

func calculate(s string) int {
   i:=0
   return parseExpr(s,&i)
}

func parseExpr(s string,i *int) int {
   op:="+"
   left,right:=0,0
   // 使用i指针来记录当前的位置
   for *i< len(s) {
      // 首先确保我们的字符串不是空格
      if string(s[*i]) != " " {
         // 然后我们就解析数字，这我们i会解析到操作符所在的位置
         n:=parseNum(s,i)
         // 下面判断操作类型，并进行不同的计算
         switch op {
         case "+":
            // 这里我们让right等于n，相当于暂存
            left+=right;right=n
         case "-":
            left+=right;right=-n
         case "*":
            // 如果是*的话优先级更高，优先计算
            right*=n
         case "/":
            right/=n
         }
         // 确保i不越界的情况下我们获取当前的操作符
         if *i < len(s) {
            op = string(s[*i])
         }
      }
      *i++
   }
   return left+right
}

// 解析数字
func parseNum(s string,i *int) int {
   n:=0
   // 我们这里不断一位一位进行解析，直到解析到操作符为止
   for *i< len(s) && unicode.IsDigit(rune(s[*i])) {
      n = 10*n + (int(s[*i]) - 48)
      *i++
   }
   return n
}

字符串匹配

实现strStr()

28. 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com) (opens new window)

这个其实就是字符串搜索算法了，字符串搜索有两种，一是BF算法，二是KMP算法

BF算法如下，调了好久。。。我太菜了，害

func strStr(haystack string, needle string) int {
   i,j:=0,0
   h,n:=len(haystack),len(needle)
   if needle==""{
      return 0
   }
   if n>h {
      return -1
   }
   for i < h {
      if haystack[i]==needle[j] {
         tmp:=i
         for tmp < h && j< n && haystack[tmp] == needle[j] {
            tmp++
            j++
         }
         if j > n-1 {
            return i
         } else {
             j=0
         }
      }
      i++
   }
   return -1
}

KMP解法如下，现在还太菜了，等我研究透了在回看

func strStr(haystack string, needle string) int {
	k,n,p:=-1,len(haystack),len(needle)
	// 如果need为0，那么我们直接返回0
	if p == 0 {
		return 0
	}
	// 初始化next数组
	next:=make([]int,p)
	for i := 0; i < p; i++ {
		next[i] = -1
	}
	// 计算next数组
	calNext(needle,next)
	// 开始进行字符串查找
	for i := 0; i < n; i++ {
		// k表示needle的位置，如果为-1，那么我们就先不计算
		for k > -1 && needle[k+1] != haystack[i] {
			k=next[k]
		}
		// 这里我们
		if needle[k+1] == haystack[i] {
			k++
		}
		if k == p-1 {
			return i-p+1
		}
	}
	return -1
}

// 计算next数组
// 简单介绍一next数组
// ababa 生成的是 -1 -1 0 1 2
func calNext(needle string,next []int)  {
	// 默认情况下，我们的next数组下标为-1（第一个一定是-1）
	p:=-1
	// 然后我们从1开始往后面进行计算
	for j := 1; j < len(needle); j++ {
		// 这里我们使用回溯来计算next数组
		for p > -1 && needle[p+1] != needle[j] {
			p = next[p]
		}
		// 当有一位相同时，p要不断++
		if needle[p+1]==needle[j] {
			p++
		}
		next[j] = p
	}
}