字符串相关算法

转换成小写字母

func toLowerCase(str string) string {
    tmp := []byte(str)
    for i := 0; i < len(tmp); i++ {
        if tmp[i] >= 'A' && tmp[i] <= 'Z' {
            tmp[i] += 32
        }
    }
    return string(tmp)
}

最后一个单词长度

func lengthOfLastWord(s string) int {
	tail := len(s) - 1
	// 找到第一个不是空的
	for tail >= 0 && s[tail] == ' ' {
		tail--
	}
	if tail < 0 {
		return 0
	}
	//  从第一个不是空的往前找，找到第一个是空的
	head := tail
	for head >= 0 && s[head] != ' ' {
		head--
	}
	return tail - head
}

字符串中第一个唯一字符

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

反转字符串问题

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

// 每咯2k反转前k个
func reverseStr(s string, k int) string {
    tmp := []byte(s)
    i := 0
    for i < len(tmp) {
        l := i
        r := i + k - 1
        if r > len(s) - 1{
            r = len(s) - 1
        }
        for k := l; k < r; k++ {
            tmp[k], tmp[r] = tmp[r], tmp[k]
            r--
        }
        i += 2 * k
    }
    return string(tmp)
}

// 翻转字符串里的单词
func reverseWords(s string) string {
    tmp := []string{}
    single := ""
    for i := 0; i < len(s); i++ {
        if s[i] == ' ' {
            if single != "" {
                tmp = append(tmp, single)
            }
            single = ""
        } else {
            single += string(s[i])
            if i == len(s) - 1 {
                tmp = append(tmp, single)
            }
        }
    }
    reverseAll(tmp)
    res := ""
    for _, v := range tmp {
        res += (" " + string(v))
    } 
    return res[1:]
}

func reverseAll(s []string) {
    for i := 0; i< len(s)>>1; i++ {
        s[i], s[len(s) - i -1] = s[len(s) - i -1], s[i]
    }
}

// 反转字符串中的单词3
func reverseWords(s string) string {
    tmp := strings.Split(s, " ")
    for i := 0; i < len(tmp); i++ {
        tmp[i] = reverSingle([]byte(tmp[i]))
    }
    return strings.Join(tmp, " ")
}

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

// 指针解法
func reverseWords(s string) string {
	b :=[]byte(s)
	l :=0
	for i,v :=range s{
		if v==' '||i==len(s)-1{
			r :=i-1
			if i==len(s)-1{
				r =i
			}
			for l<r{
				b[l],b[r] =b[r],b[l]
				l++
				r--
			}
			l=i+1
		}
	}
	return string(b)
}

仅仅反转字母

// 双指针反转
func reverseOnlyLetters(S string) string {
	tmp := []byte(S)
	for i, j := 0, len(tmp)-1; i < j; {
		for i < j && !isLetter(tmp[i]) {
			i++
		}
		for i < j && !isLetter(tmp[j]) {
			j--
		}
		tmp[i], tmp[j] = tmp[j], tmp[i]
		i++
		j--
	}
	return string(tmp)
}

func isLetter(c byte) bool {
	if c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' {
		return true
	}
	return false
}

同构字符串

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) { return false }
    tmps := make(map[byte]byte, len(s))
    tmpt := make(map[byte]byte, len(t))
    for i := 0; i < len(s); i++ {
        if _, ok := tmps[s[i]]; !ok {
            tmps[s[i]] = t[i]
        }
        if _, ok := tmpt[t[i]]; !ok {
            tmpt[t[i]] = s[i]
        }
        if tmps[s[i]] != t[i] { return false }
        if tmpt[t[i]] != s[i] { return false }
        
    }
    return true
}

验证回文串

func isPalindrome(s string) bool {
    i := 0
    j := len(s) - 1
    s = strings.ToLower(s)
    for i < j {
        for i < j && !validS(s[i]) { i++ }
        for i < j && !validS(s[j]) { j-- }
        if s[i] != s[j] { return false }
        i++
        j--
    }
    return true
}

func validS(i byte) bool {
    if (i >= 'a' && i <= 'z') || (i >= 'A' && i <= 'Z') || (i >= '0' && i <= '9') {
        return true
    }
    return false
}

// 验证回文串2，最多删除一个字符后是不是回文串
func validPalindrome(s string) bool {
    l, r := 0, len(s) - 1
    for l < r {
        if s[l] == s[r] {
            l++
            r--
        } else {
            flag1, flag2 := true, true
            // 两种情况，删除后还得继续看里面的是不是回文串，两种情况都验证
            for i, j := l, r- 1; i < j; i, j = i + 1, j - 1 {
                if s[i] != s[j] {
                    flag1 =false
                    break
                }
            }
            for i, j := l + 1, r; i < j; i, j = i + 1, j - 1{
                if s[i] != s[j] {
                    flag2 = false
                    break
                }
            }
            return flag1 || flag2
        }
    }
    return true
}

最长回文子串

// 中心扩展法
func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    start, end := 0, 0
    // 遍历，中心扩展
    for i := 0; i < len(s); i++ {
        // 奇数情况
        l1, r1 := expandS(s, i, i)
        // 偶数情况
        l2, r2 := expandS(s, i, i + 1)
        if r1 - l1 > end - start {
            start = l1
            end = r1
        }
        if r2 - l2 > end - start {
            start = l2
            end = r2
        }
    }
    return s[start:end + 1]
}

func expandS(s string, l, r int) (int, int) {
    for l >= 0 && r <= len(s) - 1 && s[l] == s[r] {
        l--
        r++
    }
    return l + 1, r - 1
}

// 动态规划
func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    dp := make([][]bool, len(s))
    for i := 0; i < len(s); i++ {
        dp[i] = make([]bool, len(s))
    }
    start := 0
    maxLen := 1
    for i := 0; i < len(s); i++ {
        for j := 0; j < i; j++ {
            switch {
            // 同一个字符串，肯定是
            case i == j: dp[j][i] = true
            // 相等的情况下，如果长度小于2，肯定是，或者里面的是回文串
            case s[i] == s[j] && (i - j <= 2 || dp[j + 1][i - 1]): dp[j][i] = true
            default:  dp[j][i] = false 
            }
            // 记录最大长度与起始位置
            if dp[j][i] {
                curLen := i - j + 1
                if curLen > maxLen {
                    maxLen = curLen
                    start = j
                }
            }
        }
    }
    return s[start:start + maxLen]
}