LeetCode Go · 字符串（1）

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

6. Z 字形变换

中等1 种解法

标签：字符串

题目、示例与约束

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

1 <= s.length <= 1000
s 由英文字母（小写和大写）、',' 和 '.' 组成
1 <= numRows <= 1000

方法一：模拟 · Go 实现

思考

按照 Z 字形将字符填入网格再按行读出，时间与空间均为线性。 $n \leq 10^{3}$ 可以接受，然而网格中多数位置为空，列这一维并不出现在最终输出中。

决定答案的只有每个字符所在的行，以及同一行内的相对顺序。行号沿 $0, 1, \dots, numRows - 1$ 往复变化，到达顶端或底端后改变方向。

为此只需维护 $numRows$ 个列表，用方向变量 $k$ 在边界处取反。将 $k$ 的初值设为 $- 1$ ，遇到第一行时立即翻转为向下。当 $numRows = 1$ 时顶与底重合，应直接返回原串，否则会在同一行上反复转向。

我们用一个二维数组 $g$ 来模拟 Z 字形排列的过程，其中 $g [i] [j]$ 表示第 $i$ 行第 $j$ 列的字符。初始时 $i = 0$ ，另外我们定义一个方向变量 $k$ ，初始时 $k = - 1$ ，表示向上走。

我们从左到右遍历字符串 $s$ ，每次遍历到一个字符 $c$ ，将其追加到 $g [i]$ 中。如果此时 $i = 0$ 或者 $i = numRows - 1$ ，说明当前字符位于 Z 字形排列的拐点，我们将 $k$ 的值反转，即 $k = - k$ 。接下来，我们将 $i$ 的值更新为 $i + k$ ，即向上或向下移动一行。继续遍历下一个字符，直到遍历完字符串 $s$ ，我们返回 $g$ 中所有行拼接后的字符串即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func convert(s string, numRows int) string {
	if numRows == 1 {
		return s
	}
	g := make([][]byte, numRows)
	i, k := 0, -1
	for _, c := range s {
		g[i] = append(g[i], byte(c))
		if i == 0 || i == numRows-1 {
			k = -k
		}
		i += k
	}
	return string(bytes.Join(g, nil))
}

力扣原题 · Doocs 题解来源

8. 字符串转换整数 (atoi)

中等1 种解法

标签：字符串

题目、示例与约束

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数。

函数 myAtoi(string s) 的算法如下：

空格：读入字符串并丢弃无用的前导空格（" "）
符号：检查下一个字符（假设还未到字符末尾）为 '-' 还是 '+'。如果两者都不存在，则假定结果为正。
转换：通过跳过前置零来读取该整数，直到遇到非数字字符或到达字符串的结尾。如果没有读取数字，则结果为0。
舍入：如果整数数超过 32 位有符号整数范围 [−2³¹, 2³¹− 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2³¹ 的整数应该被舍入为 −2³¹ ，大于 2³¹− 1 的整数应该被舍入为 2³¹− 1 。

返回整数作为最终结果。

示例 1：

输入：s = "42"

输出：42

解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。

带下划线线的字符是所读的内容，插入符号是当前读入位置。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^

示例 2：

输入：s = " -042"

输出：-42

解释：

第 1 步："   -042"（读入前导空格，但忽视掉）
            ^
第 2 步："   -042"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -042"（读入 "042"，在结果中忽略前导零）
               ^

示例 3：

输入：s = "1337c0d3"

输出：1337

解释：

第 1 步："1337c0d3"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："1337c0d3"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："1337c0d3"（读入 "1337"；由于下一个字符不是一个数字，所以读入停止）
             ^

示例 4：

输入：s = "0-1"

输出：0

解释：

第 1 步："0-1" (当前没有读入字符，因为没有前导空格)
         ^
第 2 步："0-1" (当前没有读入字符，因为这里不存在 '-' 或者 '+')
         ^
第 3 步："0-1" (读入 "0"；由于下一个字符不是一个数字，所以读入停止)
          ^

示例 5：

输入：s = "words and 987"

输出：0

解释：

读取在第一个非数字字符“w”处停止。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

方法一：遍历字符串 · Go 实现

思考

转换规则只需从左到右扫描一遍，时间复杂度为 $O (n)$ ， $n \leq 200$ 可以接受。顺序不可颠倒：符号出现在数字之前，数字必须连续，一旦遇到非数字就应停止；最后还要把结果限制在 $32$ 位整数范围内。

若不允许使用 $64$ 位整数，则不能先算出完整结果再截断。我们累加绝对值，每次乘 $10$ 之前与 $⌊ (2^{31} - 1) / 10 ⌋$ 比较，一旦越界则按符号分别返回 $2^{31} - 1$ 或 $- 2^{31}$ 。正负情形共用同一上界，最后再乘以 $sign$ ；空串或全空格没有数字，返回 $0$ 。

我们首先判断字符串是否为空，如果是，直接返回 $0$ 。

否则，我们需要遍历字符串，跳过前导空格，判断第一个非空格字符是否为正负号。

接着遍历后面的字符，如果是数字，我们判断添加该数字是否会导致整数溢出，如果会，我们根据正负号返回结果。否则我们将数字添加到结果中。继续遍历后面的字符，直到遇到非数字字符或者遍历结束。

遍历结束后，我们根据正负号返回结果。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串的长度。我们只需要依次处理所有字符。空间复杂度 $O (1)$ 。

同面试题 67. 把字符串转换成整数。

func myAtoi(s string) int {
	i, n := 0, len(s)
	num := 0

	for i < n && s[i] == ' ' {
		i++
	}
	if i == n {
		return 0
	}

	sign := 1
	if s[i] == '-' {
		sign = -1
		i++
	} else if s[i] == '+' {
		i++
	}

	for i < n && s[i] >= '0' && s[i] <= '9' {
		num = num*10 + int(s[i]-'0')
		i++
		if num > math.MaxInt32 {
			break
		}
	}

	if num > math.MaxInt32 {
		if sign == -1 {
			return math.MinInt32
		}
		return math.MaxInt32
	}
	return sign * num
}

力扣原题 · Doocs 题解来源

38. 外观数列

中等1 种解法

标签：字符串

题目、示例与约束

「外观数列」是一个数位字符串序列，由递归公式定义：

countAndSay(1) = "1"
countAndSay(n) 是 countAndSay(n-1) 的行程长度编码。

行程长度编码（RLE）是一种字符串压缩方法，其工作原理是通过将每个最大连续相同字符组替换为该组的长度后加上该字符本身。例如，要压缩字符串 "3322251" ，我们将 "33" 用 "23" 替换，将 "222" 用 "32" 替换，将 "5" 用 "15" 替换并将 "1" 用 "11" 替换。因此压缩后字符串变为 "23321511"。

给定一个整数 n ，返回 外观数列 的第 n 个元素。

示例 1：

输入：n = 4

输出："1211"

解释：

countAndSay(1) = "1"

countAndSay(2) = "1" 的行程长度编码 = "11"

countAndSay(3) = "11" 的行程长度编码 = "21"

countAndSay(4) = "21" 的行程长度编码 = "1211"

示例 2：

输入：n = 1

输出："1"

解释：

这是基本情况。

提示：

1 <= n <= 30

进阶：你能迭代解决该问题吗？

方法一 · Go 实现

思考

第 $n$ 项由第 $n - 1$ 项描述而来，没有更直接的通项公式。 $n \leq 30$ ，从 "1" 出发迭代 $n - 1$ 次即可。

每一项都是对上一项做行程长度编码：将连续相同字符写成「次数 + 字符」。我们可以用双指针扫描当前串 $s$ ，把每一段的长度与字符追加到新串。题目进阶要求使用迭代，可以避免递归带来的调用栈开销。

func countAndSay(n int) string {
	s := "1"
	for k := 0; k < n-1; k++ {
		t := &strings.Builder{}
		i := 0
		for i < len(s) {
			j := i
			for j < len(s) && s[j] == s[i] {
				j++
			}
			t.WriteString(strconv.Itoa(j - i))
			t.WriteByte(s[i])
			i = j
		}
		s = t.String()
	}
	return s
}

力扣原题 · Doocs 题解来源

58. 最后一个单词的长度

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

提示：

1 <= s.length <= 10⁴
s 仅有英文字母和空格 ' ' 组成
s 中至少存在一个单词

方法一：逆向遍历 + 双指针 · Go 实现

思考

题目保证至少有一个单词，答案只取决于最后一个单词的长度。若按空格切分再取末段， $n \leq 10^{4}$ 可以通过，但会扫完整串并分配若干子串。

中间的单词无需处理。最后一个单词贴在串尾，其右侧可能还有空格。

因此从右向左先跳过尾部空格，再继续走到该单词的左边界，两端下标之差即为长度。

我们从字符串 $s$ 末尾开始遍历，找到第一个不为空格的字符，即为最后一个单词的最后一个字符，下标记为 $i$ 。然后继续向前遍历，找到第一个为空格的字符，即为最后一个单词的第一个字符的前一个字符，记为 $j$ 。那么最后一个单词的长度即为 $i - j$ 。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 长度。空间复杂度 $O (1)$ 。

func lengthOfLastWord(s string) int {
	i := len(s) - 1
	for i >= 0 && s[i] == ' ' {
		i--
	}
	j := i
	for j >= 0 && s[j] != ' ' {
		j--
	}
	return i - j
}

力扣原题 · Doocs 题解来源

65. 有效数字

困难1 种解法

标签：字符串

题目、示例与约束

给定一个字符串 s ，返回 s 是否是一个 有效数字。

例如，下面的都是有效数字："2", "0089", "-0.1", "+3.14", "4.", "-.9", "2e10", "-90E3", "3e+7", "+6e-1", "53.5e93", "-123.456e789"，而接下来的不是："abc", "1a", "1e", "e3", "99e2.5", "--6", "-+3", "95a54e53"。

一般的，一个 有效数字 可以用以下的规则之一定义：

一个整数后面跟着一个 可选指数。
一个小数后面跟着一个 可选指数。

一个整数定义为一个 可选符号 '-' 或 '+' 后面跟着数字。

一个小数定义为一个 可选符号 '-' 或 '+' 后面跟着下述规则：

数字后跟着一个 小数点 .。
数字后跟着一个 小数点 . 再跟着数位。
一个 小数点 . 后跟着数位。

指数定义为指数符号 'e' 或 'E'，后面跟着一个整数。

数字定义为一个或多个数位。

示例 1：

输入：s = "0"

输出：true

示例 2：

输入：s = "e"

输出：false

示例 3：

输入：s = "."

输出：false

提示：

1 <= s.length <= 20
s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，或者点 '.' 。

方法一：分情况讨论 · Go 实现

思考

有效数字由可选符号、整数或小数，以及可选指数组成，形态较多。字符串长度 $n \leq 20$ ，用正则或语言自带的解析函数即可判定，但题目要求自行实现。

规则彼此约束：小数点不能出现在指数部分，e 或 E 前后均须有数字，指数仍可带符号，单独的 . 或 + 均不合法。因此从左至右扫描一遍即可：先处理开头的符号，再用 $d o t$ 与 $e$ 分别限制小数点与指数至多出现一次，遇非法字符或位置立即返回。额外空间为常数。

首先，我们判断字符串是否以正负号开头，如果是，将指针 $i$ 向后移动一位。如果此时指针 $i$ 已经到达字符串末尾，说明字符串只有一个正负号，返回 false。

如果当前指针 $i$ 指向的字符是小数点，并且小数点后面没有数字，或者小数点后是一个 e 或 E，返回 false。

接着，我们用两个变量 $d o t$ 和 $e$ 分别记录小数点和 e 或 E 的个数。

用指针 $j$ 指向当前字符：

如果当前字符是小数点，并且此前出现过小数点或者 e 或 E，返回 false。否则，我们将 $d o t$ 加一；
如果当前字符是 e 或 E，并且此前出现过 e 或 E，或者当前字符是开头或结尾，返回 false。否则，我们将 $e$ 加一；然后判断下一个字符是否是正负号，如果是，将指针 $j$ 向后移动一位。如果此时指针 $j$ 已经到达字符串末尾，返回 false；
如果当前字符不是数字，返回 false。

遍历完字符串后，返回 true。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串长度。空间复杂度 $O (1)$ 。

func isNumber(s string) bool {
	i, n := 0, len(s)
	if s[i] == '+' || s[i] == '-' {
		i++
	}
	if i == n {
		return false
	}
	if s[i] == '.' && (i+1 == n || s[i+1] == 'e' || s[i+1] == 'E') {
		return false
	}
	var dot, e int
	for j := i; j < n; j++ {
		if s[j] == '.' {
			if e > 0 || dot > 0 {
				return false
			}
			dot++
		} else if s[j] == 'e' || s[j] == 'E' {
			if e > 0 || j == i || j == n-1 {
				return false
			}
			e++
			if s[j+1] == '+' || s[j+1] == '-' {
				j++
				if j == n-1 {
					return false
				}
			}
		} else if s[j] < '0' || s[j] > '9' {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

68. 文本左右对齐

困难1 种解法

标签：数组、字符串、模拟

题目、示例与约束

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意:

单词是指由非空格字符组成的字符序列。
每个单词的长度大于 0，小于等于 maxWidth。
输入单词数组 words 至少包含一个单词。

示例 1:

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

示例 2:

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。

示例 3:

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]

提示:

1 <= words.length <= 300
1 <= words[i].length <= 20
words[i] 由小写英文字母和符号组成
1 <= maxWidth <= 100
words[i].length <= maxWidth

方法一：模拟 · Go 实现

思考

题目要求尽可能多地往每一行放置单词，再用空格补齐到 $maxWidth$ 。单词数不超过 $300$ 、行宽不超过 $100$ ，从左到右贪心取词即可，不必回溯。

复杂度并不构成瓶颈，需要仔细处理的是空格分配：最后一行以及只含一个单词的行必须左对齐；其余行应将多余空格尽量均分，不能均分时左侧间隙多放一格。因此先取出本行能放下的单词，再按是否为末行、单词数是否为 $1$ 分成两种排版。

根据题意模拟即可，注意，如果是最后一行，或者这一行只有一个单词，那么要左对齐，否则要均匀分配空格。

时间复杂度 $O (L)$ ，空间复杂度 $O (L)$ 。其中 $L$ 为所有单词的长度之和。

func fullJustify(words []string, maxWidth int) (ans []string) {
	for i, n := 0, len(words); i < n; {
		t := []string{words[i]}
		cnt := len(words[i])
		i++
		for i < n && cnt+1+len(words[i]) <= maxWidth {
			cnt += 1 + len(words[i])
			t = append(t, words[i])
			i++
		}
		if i == n || len(t) == 1 {
			left := strings.Join(t, " ")
			right := strings.Repeat(" ", maxWidth-len(left))
			ans = append(ans, left+right)
			continue
		}
		spaceWidth := maxWidth - (cnt - len(t) + 1)
		w := spaceWidth / (len(t) - 1)
		m := spaceWidth % (len(t) - 1)
		row := strings.Builder{}
		for j, s := range t[:len(t)-1] {
			row.WriteString(s)
			row.WriteString(strings.Repeat(" ", w))
			if j < m {
				row.WriteString(" ")
			}
		}
		row.WriteString(t[len(t)-1])
		ans = append(ans, row.String())
	}
	return
}

力扣原题 · Doocs 题解来源

214. 最短回文串

困难2 种解法

标签：字符串、字符串匹配、Manacher 算法、哈希函数、滚动哈希、KMP 算法、扩展 KMP

题目、示例与约束

给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。

示例 1：

输入：s = "aacecaaa"
输出："aaacecaaa"

示例 2：

输入：s = "abcd"
输出："dcbabcd"

提示：

0 <= s.length <= 5 * 10⁴
s 仅由小写英文字母组成

方法一：字符串哈希 · Go 实现

思考

在 $s$ 前面补最少字符使其回文，等价于找出 $s$ 的最长回文前缀，再把剩余后缀反转接到前面。枚举前缀并判回文偏慢。

滚动维护前缀哈希与其反转哈希，二者相等则更新最长回文前缀长度；最后把未覆盖的后缀反转拼到 $s$ 前。

字符串哈希是把一个任意长度的字符串映射成一个非负整数，并且其冲突的概率几乎为 0。字符串哈希用于计算字符串哈希值，快速判断两个字符串是否相等。

取一固定值 BASE，把字符串看作是 BASE 进制数，并分配一个大于 0 的数值，代表每种字符。一般来说，我们分配的数值都远小于 BASE。例如，对于小写字母构成的字符串，可以令 a=1, b=2, ..., z=26。取一固定值 MOD，求出该 BASE 进制对 M 的余数，作为该字符串的 hash 值。

一般来说，取 BASE=131 或者 BASE=13331，此时 hash 值产生的冲突概率极低。只要两个字符串 hash 值相同，我们就认为两个字符串是相等的。通常 MOD 取 2^64，C++ 里，可以直接使用 unsigned long long 类型存储这个 hash 值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 2^64 取模，这样可以避免低效取模运算。

除了在极特殊构造的数据上，上述 hash 算法很难产生冲突，一般情况下上述 hash 算法完全可以出现在题目的标准答案中。我们还可以多取一些恰当的 BASE 和 MOD 的值（例如大质数），多进行几组 hash 运算，当结果都相同时才认为原字符串相等，就更加难以构造出使这个 hash 产生错误的数据。

对于本题，问题等价于找到字符串 s 的最长回文前缀。

记 s 的长度为 n，其最长回文前缀的长度为 m，将 s 的后 n-m 个字符反序并添加到 s 的前面即可构成最短回文串。

func shortestPalindrome(s string) string {
	n := len(s)
	base, mod := 131, int(1e9)+7
	prefix, suffix, mul := 0, 0, 1
	idx := 0
	for i, c := range s {
		t := int(c-'a') + 1
		prefix = (prefix*base + t) % mod
		suffix = (suffix + t*mul) % mod
		mul = (mul * base) % mod
		if prefix == suffix {
			idx = i + 1
		}
	}
	if idx == n {
		return s
	}
	x := []byte(s[idx:])
	for i, j := 0, len(x)-1; i < j; i, j = i+1, j-1 {
		x[i], x[j] = x[j], x[i]
	}
	return string(x) + s
}

方法二：KMP 算法 · Go 实现

思考

字符串哈希存在冲突可能。把 $s$ 与其反串拼接后求 KMP 的 $n e x t$ ，末位值即为最长回文前缀长度。

从而在线性时间内得到同一构造，无需取模哈希。

根据题目描述，我们需要将字符串 $s$ 反转，得到字符串 $rev$ ，然后求出字符串 $r e v$ 的后缀与字符串 $s$ 的前缀的最长公共部分。我们可以使用 KMP 算法，将字符串 $s$ 与字符串 $r e v$ 连接起来，求出其最长前缀与最长后缀的最长公共部分。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func shortestPalindrome(s string) string {
	t := s + "#" + reverse(s) + "$"
	n := len(t)
	next := make([]int, n)
	next[0] = -1
	for i, j := 2, 0; i < n; {
		if t[i-1] == t[j] {
			j++
			next[i] = j
			i++
		} else if j > 0 {
			j = next[j]
		} else {
			next[i] = 0
			i++
		}
	}
	return reverse(s)[:len(s)-next[n-1]] + s
}

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

力扣原题 · Doocs 题解来源

243. 最短单词距离 🔒

简单1 种解法

标签：数组、字符串

题目、示例与约束

给定一个字符串数组 wordDict 和两个已经存在于该数组中的不同的字符串 word1 和 word2 。返回列表中这两个单词之间的最短距离。

示例 1:

输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "coding", word2 = "practice"
输出: 3

示例 2:

输入: wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出: 1

提示:

1 <= wordsDict.length <= 3 * 10⁴
1 <= wordsDict[i].length <= 10
wordsDict[i] 由小写英文字母组成
word1 和 word2 在 wordsDict 中
word1 != word2

方法一：双指针 · Go 实现

思考

$w o r d 1 \neq w o r d 2$ ，最短距离是它们最近一次出现下标之差。记下各自最近位置，扫描时更新最小值即可。

遍历数组 wordsDict，找到 word1 和 word2 的下标 $i$ 和 $j$ ，求 $i - j$ 的最小值。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为数组 wordsDict 的长度。

func shortestDistance(wordsDict []string, word1 string, word2 string) int {
	ans := 0x3f3f3f3f
	i, j := -1, -1
	for k, w := range wordsDict {
		if w == word1 {
			i = k
		}
		if w == word2 {
			j = k
		}
		if i != -1 && j != -1 {
			ans = min(ans, abs(i-j))
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

245. 最短单词距离 III 🔒

中等1 种解法

标签：数组、字符串

题目、示例与约束

给定一个字符串数组 wordsDict 和两个字符串 word1 和 word2 ，返回这两个单词在列表中出现的最短距离。

注意：word1 和 word2 是有可能相同的，并且它们将分别表示为列表中 两个独立的单词 。

示例 1：

输入：wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "coding"
输出：1

示例 2：

输入：wordsDict = ["practice", "makes", "perfect", "coding", "makes"], word1 = "makes", word2 = "makes"
输出：3

提示：

1 <= wordsDict.length <= 10⁵
1 <= wordsDict[i].length <= 10
wordsDict[i] 由小写英文字母组成
word1 和 word2 都在 wordsDict 中

方法一：分情况讨论 · Go 实现

思考

$w o r d 1$ 可以等于 $w o r d 2$ ，此时最短距离是同一单词相邻两次出现的间距；否则仍是两个词最近出现之差。

分情况维护最近下标：相同则只记上一次出现，不同则分别更新。

我们首先判断 $word1$ 和 $word2$ 是否相等：

如果相等，遍历数组 $wordsDict$ ，找到两个 $word1$ 的下标 $i$ 和 $j$ ，求 $i - j$ 的最小值。
如果不相等，遍历数组 $wordsDict$ ，找到 $word1$ 和 $word2$ 的下标 $i$ 和 $j$ ，求 $i - j$ 的最小值。

时间复杂度 $O (n)$ ，其中 $n$ 为数组 $wordsDict$ 的长度。空间复杂度 $O (1)$ 。

func shortestWordDistance(wordsDict []string, word1 string, word2 string) int {
	ans := len(wordsDict)
	if word1 == word2 {
		j := -1
		for i, w := range wordsDict {
			if w == word1 {
				if j != -1 {
					ans = min(ans, i-j)
				}
				j = i
			}
		}
	} else {
		i, j := -1, -1
		for k, w := range wordsDict {
			if w == word1 {
				i = k
			}
			if w == word2 {
				j = k
			}
			if i != -1 && j != -1 {
				ans = min(ans, abs(i-j))
			}
		}
	}
	return ans
}

func abs(x int) int {
	if x < 0 {
		return -x
	}
	return x
}

力扣原题 · Doocs 题解来源

247. 中心对称数 II 🔒

中等1 种解法

标签：递归、数组、字符串

题目、示例与约束

给定一个整数 n ，返回所有长度为 n 的 中心对称数 。你可以以 任何顺序 返回答案。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:

输入：n = 2
输出：["11","69","88","96"]

示例 2:

输入：n = 1
输出：["0","1","8"]

提示：

1 <= n <= 14

方法一：递归 · Go 实现

思考

长度为 $n$ 的中心对称数由更短的合法串左右加配对数字得到。长度为 $1$ 只有 $0, 1, 8$ ，长度为 $0$ 为空串。

$d f s (u)$ 在 $d f s (u - 2)$ 两侧加 $11, 88, 69, 96$ ；仅当 $u \neq n$ 时才允许加 $00$ ，以免出现前导零。

若长度为 $1$ ，则中心对称数只有 $0, 1, 8$ ；若长度为 $2$ ，则中心对称数只有 $11, 69, 88, 96$ 。

我们设计递归函数 $d f s (u)$ ，其返回长度为 $u$ 的中心对称数。答案为 $d f s (n)$ 。

若 $u$ 为 $0$ ，返回包含一个空串的列表，即 [""]；若 $u$ 为 $1$ ，返回列表 ["0", "1", "8"]。

若 $u$ 大于 $1$ ，我们对长度为 $u - 2$ 的所有中心对称数进行遍历，对于每个中心对称数 $v$ ，在其左右两侧分别添加 $1, 8, 6, 9$ ，即可得到长度为 u 的中心对称数。

注意，如果 $u \neq n$ ，我们还可以在中心对称数的左右两侧分别添加 $0$ 。

最终，我们将所有长度为 $n$ 的中心对称数返回即可。

时间复杂度为 $O (2^{n + 2})$ 。

相似题目：

248. 中心对称数 III 🔒

func findStrobogrammatic(n int) []string {
	var dfs func(int) []string
	dfs = func(u int) []string {
		if u == 0 {
			return []string{""}
		}
		if u == 1 {
			return []string{"0", "1", "8"}
		}
		var ans []string
		pairs := [][]string{{"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"}}
		for _, v := range dfs(u - 2) {
			for _, p := range pairs {
				ans = append(ans, p[0]+v+p[1])
			}
			if u != n {
				ans = append(ans, "0"+v+"0")
			}
		}
		return ans
	}
	return dfs(n)
}

力扣原题 · Doocs 题解来源

248. 中心对称数 III 🔒

困难1 种解法

标签：递归、数组、字符串

题目、示例与约束

给定两个字符串 low 和 high 表示两个整数 low 和 high ，其中 low <= high ，返回范围 [low, high] 内的 「中心对称数」总数。

中心对称数 是一个数字在旋转了 180 度之后看起来依旧相同的数字（或者上下颠倒地看）。

示例 1:

输入: low = "50", high = "100"
输出: 3

示例 2:

输入: low = "0", high = "0"
输出: 1

提示:

1 <= low.length, high.length <= 15
low 和 high 只包含数字
low <= high
low and high 不包含任何前导零，除了零本身。

方法一：递归 · Go 实现

思考

区间内逐个数判定中心对称偏慢。与上一题相同，按长度生成全部中心对称数，再判断是否落在 $[low, high]$ 。

长度从 $| low |$ 到 $| high |$ 枚举，生成后转整数比较即可。

若长度为 $1$ ，则中心对称数只有 $0, 1, 8$ ；若长度为 $2$ ，则中心对称数只有 $11, 69, 88, 96$ 。

我们设计递归函数 $d f s (u)$ ，其返回长度为 $u$ 的中心对称数。

若 $u$ 为 $0$ ，返回包含一个空串的列表，即 [""]；若 $u$ 为 $1$ ，返回列表 ["0", "1", "8"]。

若 $u$ 大于 $1$ ，我们对长度为 $u - 2$ 的所有中心对称数进行遍历，对于每个中心对称数 $v$ ，在其左右两侧分别添加 $1, 8, 6, 9$ ，即可得到长度为 $u$ 的中心对称数。

注意，如果 $u \neq n$ ，我们还可以在中心对称数的左右两侧分别添加 $0$ 。

设 $l o w$ 和 $h i g h$ 的长度分别为 $a$ 和 $b$ 。

接下来，我们在 $[a, . . b]$ 范围内遍历所有长度，对于每个长度 $n$ ，我们获取所有中心对称数 $d f s (n)$ ，然后判断是否在 $[l o w, h i g h]$ 范围内，若在，答案加一。

时间复杂度为 $O (2^{n + 2} \times \log n)$ 。

相似题目：

247. 中心对称数 II

func strobogrammaticInRange(low string, high string) int {
	n := 0
	var dfs func(int) []string
	dfs = func(u int) []string {
		if u == 0 {
			return []string{""}
		}
		if u == 1 {
			return []string{"0", "1", "8"}
		}
		var ans []string
		pairs := [][]string{{"1", "1"}, {"8", "8"}, {"6", "9"}, {"9", "6"}}
		for _, v := range dfs(u - 2) {
			for _, p := range pairs {
				ans = append(ans, p[0]+v+p[1])
			}
			if u != n {
				ans = append(ans, "0"+v+"0")
			}
		}
		return ans
	}
	a, b := len(low), len(high)
	l, _ := strconv.Atoi(low)
	r, _ := strconv.Atoi(high)
	ans := 0
	for n = a; n <= b; n++ {
		for _, s := range dfs(n) {
			v, _ := strconv.Atoi(s)
			if l <= v && v <= r {
				ans++
			}
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

293. 翻转游戏 🔒

简单1 种解法

标签：字符串

题目、示例与约束

你和朋友玩一个叫做「翻转游戏」的游戏。游戏规则如下：

给你一个字符串 currentState ，其中只含 '+' 和 '-' 。你和朋友轮流将连续的两个 "++" 反转成 "--" 。当一方无法进行有效的翻转时便意味着游戏结束，则另一方获胜。

计算并返回 一次有效操作 后，字符串 currentState 所有的可能状态，返回结果可以按 任意顺序 排列。如果不存在可能的有效操作，请返回一个空列表 [] 。

示例 1：

输入：currentState = "++++"
输出：["--++","+--+","++--"]

示例 2：

输入：currentState = "+"
输出：[]

提示：

1 <= currentState.length <= 500
currentState[i] 不是 '+' 就是 '-'

方法一：遍历 + 模拟 · Go 实现

思考

一步是把某一处连续两个 $+$ 翻成 $-$ 。扫描相邻对，遇到 $+ +$ 则翻转为一种后继并还原，收集全部可能。

我们遍历字符串，如果当前字符和下一个字符都是 +，那么我们就将这两个字符变成 -，然后将结果加入到结果数组中，再将这两个字符变回 +。

遍历结束后，返回结果数组即可。

时间复杂度 $O (n^{2})$ ，其中 $n$ 是字符串长度。忽略答案数组的空间复杂度，空间复杂度 $O (n)$ 或 $O (1)$ 。

func generatePossibleNextMoves(currentState string) (ans []string) {
	s := []byte(currentState)
	for i := 0; i < len(s)-1; i++ {
		if s[i] == '+' && s[i+1] == '+' {
			s[i], s[i+1] = '-', '-'
			ans = append(ans, string(s))
			s[i], s[i+1] = '+', '+'
		}
	}
	return
}

力扣原题 · Doocs 题解来源

434. 字符串中的单词数

简单2 种解法

标签：字符串

题目、示例与约束

统计字符串中的单词个数，这里的单词指的是连续的不是空格的字符。

请注意，你可以假定字符串里不包括任何不可打印的字符。

示例:

输入: "Hello, my name is John"
输出: 5
解释: 这里的单词是指连续的不是空格的字符，所以 "Hello," 算作 1 个单词。

方法一：字符串分割 · Go 实现

思考

段由空格分隔。手写扫描要处理首尾与连续空格； $split$ 默认按空白切开并丢掉空段，直接得到段数。

语言库一次遍历即可，适合作为第一解。

我们将字符串 $s$ 按照空格进行分割，然后统计不为空的单词个数。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func countSegments(s string) int {
	ans := 0
	for _, t := range strings.Split(s, " ") {
		if len(t) > 0 {
			ans++
		}
	}
	return ans
}

方法二：模拟 · Go 实现

思考

方法一分配了单词列表。若只计数，遇到「非空格且前一格是空格（或位于开头）」即新段开始，额外空间降为常数。

我们也可以直接遍历字符串的每个字符 $s[i]$ ，如果 $s[i]$ 不是空格且 $s[i-1]$ 是空格或者 $i = 0$ ，那么就说明 $s[i]$ 是一个新的单词的开始，我们就将答案加一。

遍历结束后，返回答案即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func countSegments(s string) int {
	ans := 0
	for i, c := range s {
		if c != ' ' && (i == 0 || s[i-1] == ' ') {
			ans++
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

459. 重复的子字符串

简单1 种解法

标签：字符串、字符串匹配、KMP 算法、扩展 KMP

题目、示例与约束

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2:

输入: s = "aba"
输出: false

示例 3:

输入: s = "abcabcabcabc"
输出: true
解释: 可由子串 "abc" 重复四次构成。 (或子串 "abcabc" 重复两次构成。)

提示：

1 <= s.length <= 10⁴
s 由小写英文字母组成

方法一：双倍字符串 · Go 实现

思考

判断 $s$ 是否由某一真前缀重复而成。枚举前缀长度并比较是 $O (n^{2})$ 。

构造 $s + s$ ，从下标 $1$ 起查找 $s$ ：若第一次出现的位置小于 $n$ ，说明 $s$ 在拼接串内部对齐，即存在周期。

查找从 $1$ 开始是为了避开开头的平凡匹配；位置等于 $n$ 表示只在正中间对齐，没有更小周期。

若长度为 $n$ 的字符串 $s$ 由 $m$ 个重复子串组成，将 $s$ 拼接在自身上，得到字符串 $s s$ ，长度为 $2 n$ ，此时若从下标 $1$ 开始查找 $s$ ，那么查找到的下标一定小于 $s$ 的长度。

若长度为 $n$ 的字符串 $s$ 不由重复子串组成，将 $s$ 拼接在自身上，得到字符串 $s s$ ，长度为 $2 n$ ，此时若从下标 $1$ 开始查找 $s$ ，那么查找到的下标一定等于 $s$ 的长度。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func repeatedSubstringPattern(s string) bool {
	return strings.Index(s[1:]+s, s) < len(s)-1
}

力扣原题 · Doocs 题解来源

468. 验证IP地址

中等1 种解法

标签：字符串

题目、示例与约束

给定一个字符串 queryIP。如果是有效的 IPv4 地址，返回 "IPv4" ；如果是有效的 IPv6 地址，返回 "IPv6" ；如果不是上述类型的 IP 地址，返回 "Neither" 。

有效的IPv4地址 是 “x1.x2.x3.x4” 形式的IP地址。其中 0 <= x_i <= 255 且 x_i 不能包含 前导零。例如: “192.168.1.1” 、 “192.168.1.0” 为有效IPv4地址， “192.168.01.1” 为无效IPv4地址; “192.168.1.00” 、 “192.168@1.1” 为无效IPv4地址。

一个有效的IPv6地址 是一个格式为“x1:x2:x3:x4:x5:x6:x7:x8” 的IP地址，其中:

1 <= x_i.length <= 4
x_i 是一个 十六进制字符串 ，可以包含数字、小写英文字母( 'a' 到 'f' )和大写英文字母( 'A' 到 'F' )。
在 x_i 中允许前导零。

例如 "2001:0db8:85a3:0000:0000:8a2e:0370:7334" 和 "2001:db8:85a3:0:0:8A2E:0370:7334" 是有效的 IPv6 地址，而 "2001:0db8:85a3::8A2E:037j:7334" 和 "02001:0db8:85a3:0000:0000:8a2e:0370:7334" 是无效的 IPv6 地址。

示例 1：

输入：queryIP = "172.16.254.1"
输出："IPv4"
解释：有效的 IPv4 地址，返回 "IPv4"

示例 2：

输入：queryIP = "2001:0db8:85a3:0:0:8A2E:0370:7334"
输出："IPv6"
解释：有效的 IPv6 地址，返回 "IPv6"

示例 3：

输入：queryIP = "256.256.256.256"
输出："Neither"
解释：既不是 IPv4 地址，又不是 IPv6 地址

提示：

queryIP 仅由英文字母，数字，字符 '.' 和 ':' 组成。

方法一：模拟 · Go 实现

思考

要区分 IPv4、IPv6 与非法。正则可以写，但前导零、空段、字符集等边界更容易在拆分后逐段检查。

按 . 分成 $4$ 段判 IPv4：禁止前导零，必须是 $0$ – $255$ 的数字。按 : 分成 $8$ 段判 IPv6：长度 $1$ – $4$ 且均为十六进制。都不满足则 $Neither$ 。

先 IPv4 再 IPv6，两种格式的分隔符不同，不会同时成立。空段会在长度或 $isdigit$ 检查中失败。

我们可以定义两个函数 isIPv4 和 isIPv6 来判断一个字符串是否是有效的 IPv4 地址和 IPv6 地址。

函数 isIPv4 的实现如下：

我们首先判断字符串 s 是否以 . 结尾，如果是的话，说明 s 不是一个有效的 IPv4 地址，直接返回 false。
然后我们将字符串 s 以 . 分割成一个字符串数组 ss，如果 ss 的长度不等于 4，说明 s 不是一个有效的 IPv4 地址，直接返回 false。
对于数组 ss 中的每个字符串 t，我们判断：
- 如果 t 的长度大于 1 且 t 的第一个字符是 0，说明 t 不是一个有效的 IPv4 地址，直接返回 false。
- 如果 t 不是一个数字或者 t 不在 0 到 255 的范围内，说明 t 不是一个有效的 IPv4 地址，直接返回 false。
如果上述条件都不满足，说明 s 是一个有效的 IPv4 地址，返回 true。

函数 isIPv6 的实现如下：

我们首先判断字符串 s 是否以 : 结尾，如果是的话，说明 s 不是一个有效的 IPv6 地址，直接返回 false。
然后我们将字符串 s 以 : 分割成一个字符串数组 ss，如果 ss 的长度不等于 8，说明 s 不是一个有效的 IPv6 地址，直接返回 false。
对于数组 ss 中的每个字符串 t，我们判断：
- 如果 t 的长度小于 1 或大于 4，说明 t 不是一个有效的 IPv6 地址，直接返回 false。
- 如果 t 中的字符不全是 0 到 9 和 a 到 f（不区分大小写），说明 t 不是一个有效的 IPv6 地址，直接返回 false。
如果上述条件都不满足，说明 s 是一个有效的 IPv6 地址，返回 true。

最后，我们调用 isIPv4 和 isIPv6 函数判断 queryIP 是不是一个有效的 IPv4 地址或 IPv6 地址，如果都不是，返回 Neither。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 queryIP 的长度。

func validIPAddress(queryIP string) string {
	if isIPv4(queryIP) {
		return "IPv4"
	}
	if isIPv6(queryIP) {
		return "IPv6"
	}
	return "Neither"
}

func isIPv4(s string) bool {
	if strings.HasSuffix(s, ".") {
		return false
	}
	ss := strings.Split(s, ".")
	if len(ss) != 4 {
		return false
	}
	for _, t := range ss {
		if len(t) == 0 || (len(t) > 1 && t[0] == '0') {
			return false
		}
		x := convert(t)
		if x < 0 || x > 255 {
			return false
		}
	}
	return true
}

func isIPv6(s string) bool {
	if strings.HasSuffix(s, ":") {
		return false
	}
	ss := strings.Split(s, ":")
	if len(ss) != 8 {
		return false
	}
	for _, t := range ss {
		if len(t) < 1 || len(t) > 4 {
			return false
		}
		for _, c := range t {
			if !unicode.IsDigit(c) && !strings.ContainsRune("0123456789abcdefABCDEF", c) {
				return false
			}
		}
	}
	return true
}

func convert(s string) int {
	x := 0
	for _, c := range s {
		if !unicode.IsDigit(c) {
			return -1
		}
		x = x*10 + int(c-'0')
		if x > 255 {
			return x
		}
	}
	return x
}

力扣原题 · Doocs 题解来源

482. 密钥格式化

简单1 种解法

标签：字符串

题目、示例与约束

给定一个许可密钥字符串 s，仅由字母、数字字符和破折号组成。字符串由 n 个破折号分成 n + 1 组。你也会得到一个整数 k 。

我们想要重新格式化字符串 s，使每一组包含 k 个字符，除了第一组，它可以比 k 短，但仍然必须包含至少一个字符。此外，两组之间必须插入破折号，并且应该将所有小写字母转换为大写字母。

返回 重新格式化的许可密钥 。

示例 1：

输入：S = "5F3Z-2e-9-w", k = 4
输出："5F3Z-2E9W"
解释：字符串 S 被分成了两个部分，每部分 4 个字符；
     注意，两个额外的破折号需要删掉。

示例 2：

输入：S = "2-5g-3-J", k = 2
输出："2-5G-3J"
解释：字符串 S 被分成了 3 个部分，按照前面的规则描述，第一部分的字符可以少于给定的数量，其余部分皆为 2 个字符。

提示:

1 <= s.length <= 10⁵
s 只包含字母、数字和破折号 '-'.
1 <= k <= 10⁴

方法一：模拟 · Go 实现

思考

去掉旧破折号后，从右每 $k$ 个字符一组，第一组可以更短，字母须大写。从右扫描再反转也可以，但要先知道第一组长度。

有效字符个数对 $k$ 取模得到第一组长度（模为 $0$ 则整组为 $k$ ）。从左写入大写，计数用尽就加破折号并重置为 $k$ ，最后去掉可能多写的尾部破折号。

第一组长度先算出来，从左输出就能保持「首组较短」而不用二次反转。

我们先统计出字符串 $s$ 中除去破折号之外的字符个数，并对 $k$ 取模，得到第一组字符的个数。如果为 $0$ ，则第一组字符个数为 $k$ ，否则为取模的结果。

接着我们遍历字符串 $s$ ，对于每个字符，如果是破折号，则跳过；否则将其转换为大写字母，并将其加入答案字符串中。同时，我们维护一个计数器 $c n t$ ，表示当前组还剩余的字符个数，当 $c n t$ 减为 $0$ 时，我们需要更新 $c n t$ 为 $k$ ，并且如果当前字符不是最后一个字符，我们需要在答案字符串中加入一个破折号。

最后，我们移除答案字符串末尾的破折号，并返回答案字符串。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。忽略答案字符串的空间消耗，空间复杂度 $O (1)$ 。

func licenseKeyFormatting(s string, k int) string {
	n := len(s)
	cnt := (n - strings.Count(s, "-")) % k
	if cnt == 0 {
		cnt = k
	}

	var ans strings.Builder
	for i := 0; i < n; i++ {
		c := s[i]
		if c == '-' {
			continue
		}
		if cnt == 0 {
			cnt = k
			ans.WriteByte('-')
		}
		ans.WriteRune(unicode.ToUpper(rune(c)))
		cnt--
	}

	return ans.String()
}

力扣原题 · Doocs 题解来源

520. 检测大写字母

简单1 种解法

标签：字符串

题目、示例与约束

我们定义，在以下情况时，单词的大写用法是正确的：

全部字母都是大写，比如 "USA" 。
所有字母都不是大写，比如 "leetcode" 。
只有首字母大写，比如 "Google" 。

给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。

示例 1：

输入：word = "USA"
输出：true

示例 2：

输入：word = "FlaG"
输出：false

提示：

1 <= word.length <= 100
word 由小写和大写英文字母组成

方法一：统计大写字母的个数 · Go 实现

思考

合法大小写只有三种：全小写、全大写、或仅首字母大写。扫描一遍统计大写个数即可区分。

大写个数为 $0$ 或等于长度，或恰好为 $1$ 且首字母大写，三者之一即合法。无需多次正则或复制字符串。

我们可以统计字符串中大写字母的个数，然后根据大写字母的个数判断是否符合题目要求。

如果大写字母的个数为 0 或者等于字符串的长度，那么返回 true。
如果大写字母的个数为 1 并且第一个字母是大写字母，那么返回 true。
否则返回 false。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 word 的长度。空间复杂度 $O (1)$ 。

func detectCapitalUse(word string) bool {
	cnt := 0
	for _, c := range word {
		if unicode.IsUpper(c) {
			cnt++
		}
	}
	return cnt == 0 || cnt == len(word) || (cnt == 1 && unicode.IsUpper(rune(word[0])))
}

力扣原题 · Doocs 题解来源

521. 最长特殊序列 Ⅰ

简单1 种解法

标签：字符串

题目、示例与约束

给你两个字符串 a 和 b，请返回这两个字符串中 最长的特殊序列 的长度。如果不存在，则返回 -1 。

「最长特殊序列」 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列） 。

字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。

例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。 "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。

示例 1：

输入: a = "aba", b = "cdc"
输出: 3
解释: 最长特殊序列可为 "aba" (或 "cdc")，两者均为自身的子序列且不是对方的子序列。

示例 2：

输入：a = "aaa", b = "bbb"
输出：3
解释: 最长特殊序列是 "aaa" 和 "bbb" 。

示例 3：

输入：a = "aaa", b = "aaa"
输出：-1
解释: 字符串 a 的每个子序列也是字符串 b 的每个子序列。同样，字符串 b 的每个子序列也是字符串 a 的子序列。

提示：

1 <= a.length, b.length <= 100
a 和 b 由小写英文字母组成

方法一：脑筋急转弯 · Go 实现

思考

子序列通过删字符得到。两串若完全相同，删完后仍彼此是对方的子序列，不存在「独有」的非空子序列。

若两串不等，较长者本身不可能是较短者的子序列，其长度就是最长独有子序列。比较长度并判断相等即可，不必枚举子序列。

如果字符串 a 和 b 相等，那么它们没有特殊序列，返回 -1；否则，返回长度较长的字符串的长度。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 a 和 b 中较长的字符串的长度。空间复杂度 $O (1)$ 。

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

力扣原题 · Doocs 题解来源

544. 输出比赛匹配对 🔒

中等1 种解法

标签：递归、字符串、模拟

题目、示例与约束

在 NBA 季后赛期间，我们总是安排相对强大的球队与相对弱小的球队比赛，就像让排名第 1 的球队与排名第 n 的球队比赛一样，这是一种使比赛更加有趣的好策略。

现给定 n 支球队，请以字符串的形式返回它们的最终的比赛匹配方案。

这 n 支球队从 1 到 n 进行标记，代表它们的初始排名（即，排名 1 的是最强的球队，排名 n 的是最弱的球队）。

我们将使用括号 '(' 和 ')' 以及逗号 ',' 来表示比赛的匹配情况。我们使用括号来表示匹配，逗号来表示分组。在每一轮的匹配过程中，你总是需要遵循使相对强大的球队与相对弱小的球队配对的策略。

示例 1：

输入: n = 4
输出: "((1,4),(2,3))"
解释: 
在第一轮，我们将队伍 1 和 4 配对，2 和 3 配对，以满足将强队和弱队搭配的效果。得到(1,4),(2,3).
在第二轮，(1,4) 和 (2,3) 的赢家需要进行比赛以确定最终赢家，因此需要再在外面加一层括号。
于是最终答案是((1,4),(2,3))。

示例 2：

输入: n = 8
输出: "(((1,8),(4,5)),((2,7),(3,6)))"
解释: 
第一轮: (1,8),(2,7),(3,6),(4,5)
第二轮: ((1,8),(4,5)),((2,7),(3,6))
第三轮 (((1,8),(4,5)),((2,7),(3,6)))
由于第三轮会决出最终胜者，故输出答案为(((1,8),(4,5)),((2,7),(3,6)))。

提示：

n == 2^x，并且 x 在范围 [1, 12] 内。

方法一：模拟 · Go 实现

思考

对阵按 $1$ 对 $n$ 、 $2$ 对 $n - 1$ 如此配对，并递归生成下一轮括号串。 $n$ 为 $2$ 的幂，模拟即可。

用数组存当前轮的队伍（或已生成的对阵串），每一轮把 $i$ 与 $n - 1 - i$ 包成 (a,b) 写回前半，长度减半，直到只剩一项。

我们可以用一个长度为 $n$ 的数组 $s$ 来存储每个队伍的编号，然后模拟比赛的过程。

每一轮比赛，我们将数组 $s$ 中的前 $n$ 个元素两两配对，然后将胜者的编号存入数组 $s$ 的前 $n / 2$ 个位置。然后，我们将 $n$ 减半，继续进行下一轮比赛，直到 $n$ 减半为 $1$ ，此时数组 $s$ 中的第一个元素即为最终的比赛匹配方案。

时间复杂度 $O (n \times \log n)$ ，空间复杂度 $O (n \times \log n)$ 。其中 $n$ 为队伍的数量。

func findContestMatch(n int) string {
	s := make([]string, n)
	for i := 0; i < n; i++ {
		s[i] = strconv.Itoa(i + 1)
	}
	for ; n > 1; n >>= 1 {
		for i := 0; i < n>>1; i++ {
			s[i] = fmt.Sprintf("(%s,%s)", s[i], s[n-i-1])
		}
	}
	return s[0]
}

力扣原题 · Doocs 题解来源

551. 学生出勤记录 I

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 s 表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

'A'：Absent，缺勤
'L'：Late，迟到
'P'：Present，到场

如果学生能够同时满足下面两个条件，则可以获得出勤奖励：

按 总出勤 计，学生缺勤（'A'）严格少于两天。
学生不会存在连续 3 天或连续 3 天以上的迟到（'L'）记录。

如果学生可以获得出勤奖励，返回 true ；否则，返回 false 。

示例 1：

输入：s = "PPALLP"
输出：true
解释：学生缺勤次数少于 2 次，且不存在 3 天或以上的连续迟到记录。

示例 2：

输入：s = "PPALLL"
输出：false
解释：学生最后三天连续迟到，所以不满足出勤奖励的条件。

提示：

1 <= s.length <= 1000
s[i] 为 'A'、'L' 或 'P'

方法一：字符串遍历 · Go 实现

思考

合法记录至多一个 'A'，且不能有连续三个 'L'。扫描一遍计数即可，无需正则。

统计 'A' 的个数，并检查是否出现子串 LLL。两者同时满足则返回真。字符串长度不超过 $1000$ ，线性扫描足够。

我们可以遍历字符串 $s$ ，记录字符 'A' 和字符串 "LLL" 的出现次数。如果字符 'A' 的出现次数小于 $2$ ，且字符串 "LLL" 没有出现过，则可以将该字符串视作记录合法，返回 true，否则返回 false。

时间复杂度 $O (n)$ ，其中 $n$ 是字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func checkRecord(s string) bool {
	return strings.Count(s, "A") < 2 && !strings.Contains(s, "LLL")
}

力扣原题 · Doocs 题解来源

657. 机器人能否返回原点

简单1 种解法

标签：字符串、模拟

题目、示例与约束

在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

移动顺序由字符串 moves 表示。字符 move[i] 表示其第 i 次移动。机器人的有效动作有 R（右），L（左），U（上）和 D（下）。

如果机器人在完成所有动作后返回原点，则返回 true。否则，返回 false。

注意：机器人“面朝”的方向无关紧要。 “R” 将始终使机器人向右移动一次，“L” 将始终向左移动等。此外，假设每次移动机器人的移动幅度相同。

示例 1:

输入: moves = "UD"
输出: true
解释：机器人向上移动一次，然后向下移动一次。所有动作都具有相同的幅度，因此它最终回到它开始的原点。因此，我们返回 true。

示例 2:

输入: moves = "LL"
输出: false
解释：机器人向左移动两次。它最终位于原点的左侧，距原点有两次 “移动” 的距离。我们返回 false，因为它在移动结束时没有返回原点。

提示:

1 <= moves.length <= 2 * 10⁴
moves 只包含字符 'U', 'D', 'L' 和 'R'

方法一：维护坐标 · Go 实现

思考

判断移动序列是否回到原点，只需净位移为零。

维护坐标 $(x, y)$ ，按 UDLR 加减，最后看是否都为 $0$ 。

我们可以维护一个坐标 $(x, y)$ ，分别表示机器人在水平方向和竖直方向上的移动。

遍历字符串 $moves$ ，根据当前字符的不同，更新坐标 $(x, y)$ ：

如果当前字符是 'U'，则 $y$ 加 $1$ ；
如果当前字符是 'D'，则 $y$ 减 $1$ ；
如果当前字符是 'L'，则 $x$ 减 $1$ ；
如果当前字符是 'R'，则 $x$ 加 $1$ 。

最后，判断 $x$ 和 $y$ 是否都为 $0$ 即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $moves$ 的长度。空间复杂度 $O (1)$ 。

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

力扣原题 · Doocs 题解来源

686. 重复叠加字符串匹配

中等1 种解法

标签：字符串、字符串匹配、KMP 算法、Boyer–Moore 算法、扩展 KMP

题目、示例与约束

给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。

注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。

示例 1：

输入：a = "abcd", b = "cdabcdab"
输出：3
解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。

示例 2：

输入：a = "a", b = "aa"
输出：2

示例 3：

输入：a = "a", b = "a"
输出：1

示例 4：

输入：a = "abc", b = "wxyz"
输出：-1

提示：

1 <= a.length <= 10⁴
1 <= b.length <= 10⁴
a 和 b 由小写英文字母组成

方法一 · Go 实现

思考

$a$ 重复若干次后要包含 $b$ 。次数下界是 $⌈ | b | / | a | ⌉$ ，再多两三次即可覆盖跨边界的匹配； $| a |, | b |$ 不大，直接拼接判断即可。

从该下界起至多再追加 $3$ 个 $a$ ，若 b in t 则返回次数，否则无法构成。

func repeatedStringMatch(a string, b string) int {
	m, n := len(a), len(b)
	ans := (n + m - 1) / m
	t := strings.Repeat(a, ans)
	for i := 0; i < 3; i++ {
		if strings.Contains(t, b) {
			return ans
		}
		ans++
		t += a
	}
	return -1
}

力扣原题 · Doocs 题解来源

709. 转换成小写字母

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 s ，将该字符串中的大写字母转换成相同的小写字母，返回新的字符串。

示例 1：

输入：s = "Hello"
输出："hello"

示例 2：

输入：s = "here"
输出："here"

示例 3：

输入：s = "LOVELY"
输出："lovely"

提示：

1 <= s.length <= 100
s 由 ASCII 字符集中的可打印字符组成

方法一：模拟 · Go 实现

思考

将字符串中的大写字母改为小写，长度不超过 $100$ 。直接调用库函数即可，也可以按 ASCII 自行转换。

大写与对应小写恰好相差 $32$ ，在二进制上等价于把第 $5$ 位置 $1$ 。对大写字母做按位或 $32$ 便得到小写，其余字符保持不变。

遍历每个字符，若为大写则 $ord (c) | 32$ ，再拼回字符串。时间 $O (n)$ 。

我们可以遍历字符串，对于每个大写字母，将其转换为小写字母。最后返回转换后的字符串即可。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串的长度。忽略答案的空间消耗，空间复杂度 $O (1)$ 。

func toLowerCase(s string) string {
	cs := []byte(s)
	for i, c := range cs {
		if c >= 'A' && c <= 'Z' {
			cs[i] |= 32
		}
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

722. 删除注释

中等1 种解法

标签：数组、字符串

题目、示例与约束

给一个 C++ 程序，删除程序中的注释。这个程序source是一个数组，其中source[i]表示第 i 行源码。这表示每行源码由 '\n' 分隔。

在 C++ 中有两种注释风格，行内注释和块注释。

字符串// 表示行注释，表示//和其右侧的其余字符应该被忽略。
字符串/* 表示一个块注释，它表示直到下一个（非重叠）出现的*/之间的所有字符都应该被忽略。（阅读顺序为从左到右）非重叠是指，字符串/*/并没有结束块注释，因为注释的结尾与开头相重叠。

第一个有效注释优先于其他注释。

如果字符串//出现在块注释中会被忽略。
同样，如果字符串/*出现在行或块注释中也会被忽略。

如果一行在删除注释之后变为空字符串，那么不要输出该行。即，答案列表中的每个字符串都是非空的。

样例中没有控制字符，单引号或双引号字符。

比如，source = "string s = "/* Not a comment. */";" 不会出现在测试样例里。

此外，没有其他内容（如定义或宏）会干扰注释。

我们保证每一个块注释最终都会被闭合，所以在行或块注释之外的/*总是开始新的注释。

最后，隐式换行符可以通过块注释删除。有关详细信息，请参阅下面的示例。

从源代码中删除注释后，需要以相同的格式返回源代码。

示例 1:

输入: source = ["/*Test program */", "int main()", "{ ", "  // variable declaration ", "int a, b, c;", "/* This is a test", "   multiline  ", "   comment for ", "   testing */", "a = b + c;", "}"]
输出: ["int main()","{ ","  ","int a, b, c;","a = b + c;","}"]
解释: 示例代码可以编排成这样:
/*Test program */
int main()
{ 
  // variable declaration 
int a, b, c;
/* This is a test
   multiline  
   comment for 
   testing */
a = b + c;
}
第 1 行和第 6-9 行的字符串 /* 表示块注释。第 4 行的字符串 // 表示行注释。
编排后: 
int main()
{ 
  
int a, b, c;
a = b + c;
}

示例 2:

输入: source = ["a/*comment", "line", "more_comment*/b"]
输出: ["ab"]
解释: 原始的 source 字符串是 "a/*comment\nline\nmore_comment*/b", 其中我们用粗体显示了换行符。删除注释后，隐含的换行符被删除，留下字符串 "ab" 用换行符分隔成数组时就是 ["ab"].

提示:

1 <= source.length <= 100
0 <= source[i].length <= 80
source[i] 由可打印的 ASCII 字符组成。
每个块注释都会被闭合。
给定的源码中不会有单引号、双引号或其他控制字符。

方法一：分情况讨论 · Go 实现

思考

要从源码中去掉行注释与块注释，并保留跨行块注释之外的有效字符。源码总长有限，一次扫描即可，难点在状态：是否正处在块注释中，以及行注释会吃掉本行剩余部分。

块注释可以跨行，因此状态必须带到下一行；行注释只作用于当前行。两种注释都以两字符记号开头，扫描时要优先识别 /*、*/、//，避免把记号拆开当普通字符。

用 $blockComment$ 与缓冲 $t$ ：块内只寻找结束符；块外遇 // 结束本行，遇 /* 进入块，否则收入 $t$ 。一行结束且不在块内、缓冲非空时才形成答案的一行，这样跨行拼接也自然成立。

我们用一个变量来表示当前是否处于块注释中，初始时 $blockComment$ 为 false；用一个变量 $t$ 来存储当前行的有效字符。

接下来，遍历每一行，分情况讨论：

如果当前处于块注释中，那么如果当前字符和下一个字符是 '*/'，说明块注释结束，我们将 $blockComment$ 置为 false，并且跳过这两个字符；否则，我们继续保持块注释状态，不做任何操作；

如果当前不处于块注释中，那么如果当前字符和下一个字符是 '/*'，说明块注释开始，我们将 $blockComment$ 置为 true，并且跳过这两个字符；如果当前字符和下一个字符是 '//'，那么说明行注释开始，我们直接退出当前行的遍历；否则，说明当前字符是有效字符，我们将其加入 $t$ 中；

遍历完当前行后，如果 $blockComment$ 为 false，并且 $t$ 不为空，说明当前行是有效行，我们将其加入答案数组中，并且清空 $t$ 。继续遍历下一行。

时间复杂度 $O (L)$ ，空间复杂度 $O (L)$ ，其中 $L$ 是源代码的总长度。

func removeComments(source []string) (ans []string) {
	t := []byte{}
	blockComment := false
	for _, s := range source {
		m := len(s)
		for i := 0; i < m; i++ {
			if blockComment {
				if i+1 < m && s[i] == '*' && s[i+1] == '/' {
					blockComment = false
					i++
				}
			} else {
				if i+1 < m && s[i] == '/' && s[i+1] == '*' {
					blockComment = true
					i++
				} else if i+1 < m && s[i] == '/' && s[i+1] == '/' {
					break
				} else {
					t = append(t, s[i])
				}
			}
		}
		if !blockComment && len(t) > 0 {
			ans = append(ans, string(t))
			t = []byte{}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

796. 旋转字符串

简单1 种解法

标签：字符串、字符串匹配

题目、示例与约束

给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。

s 的 旋转操作 就是将 s 最左边的字符移动到最右边。

例如, 若 s = 'abcde'，在旋转一次之后结果就是'bcdea' 。

示例 1：

输入： s = "abcde", goal = "cdeab"

输出： true

解释：

将 s 向左旋转 2 个位置，即可将 "ab" 移动到字符串末尾，得到 "cdeab"，与 goal 相等。

示例 2：

输入： s = "abcde", goal = "abced"

输出： false

解释：

无论对 s 进行多少次旋转，都无法得到 "abced"。由于字符的相对顺序不同，因此 goal 不是 s 的旋转结果。

提示:

1 <= s.length, goal.length <= 100
s 和 goal 由小写英文字母组成

方法一 · Go 实现

思考

判断 $g o a l$ 是否为 $s$ 的旋转。长度不同则否；否则 $g o a l$ 必是 $s + s$ 的子串，一次查找即可。

func rotateString(s string, goal string) bool {
	return len(s) == len(goal) && strings.Contains(s+s, goal)
}

力扣原题 · Doocs 题解来源

806. 写字符串需要的行数

简单1 种解法

标签：数组、字符串

题目、示例与约束

我们要把给定的字符串 S 从左到右写到每一行上，每一行的最大宽度为100个单位，如果我们在写某个字母的时候会使这行超过了100 个单位，那么我们应该把这个字母写到下一行。我们给定了一个数组 widths ，这个数组 widths[0] 代表 'a' 需要的单位， widths[1] 代表 'b' 需要的单位，...， widths[25] 代表 'z' 需要的单位。

现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

示例 1:
输入: 
widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "abcdefghijklmnopqrstuvwxyz"
输出: [3, 60]
解释: 
所有的字符拥有相同的占用单位10。所以书写所有的26个字母，
我们需要2个整行和占用60个单位的一行。

示例 2:
输入: 
widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10]
S = "bbbcccdddaaa"
输出: [2, 4]
解释: 
除去字母'a'所有的字符都是相同的单位10，并且字符串 "bbbcccdddaa" 将会覆盖 9 * 10 + 2 * 4 = 98 个单位.
最后一个字母 'a' 将会被写到第二行，因为第一行只剩下2个单位了。
所以，这个答案是2行，第二行有4个单位宽度。

注:

字符串 S 的长度在 [1, 1000] 的范围。
S 只包含小写字母。
widths 是长度为 26的数组。
widths[i] 值的范围在 [2, 10]。

方法一：模拟 · Go 实现

思考

字母宽度已知、每行宽度固定为 $100$ ，需要模拟书写过程得到行数与最后一行占用宽度。字符串长度有限，按字母依次累加即可。

若当前行剩余宽度放不下该字母，则换行并把该字母作为新行的起始宽度。最后返回行数与最后一行的宽度。

我们定义两个变量 lines 和 last，分别表示行数和最后一行的宽度，初始时 lines = 1，last = 0。

遍历字符串 $s$ ，对于每个字符 $c$ ，计算其宽度 $w$ ，如果 $l a s t + w \leq 100$ ，则将 $w$ 加到 last 上，否则行数 lines 加一，并且 last 重置为 $w$ 。

最后返回 lines 和 last 构成的数组。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func numberOfLines(widths []int, s string) []int {
	lines, last := 1, 0
	for _, c := range s {
		w := widths[c-'a']
		if last+w <= 100 {
			last += w
		} else {
			lines++
			last = w
		}
	}
	return []int{lines, last}
}

力扣原题 · Doocs 题解来源

824. 山羊拉丁文

简单1 种解法

标签：字符串

题目、示例与约束

给你一个由若干单词组成的句子 sentence ，单词间由空格分隔。每个单词仅由大写和小写英文字母组成。

请你将句子转换为 “山羊拉丁文（Goat Latin）”（一种类似于猪拉丁文 - Pig Latin 的虚构语言）。山羊拉丁文的规则如下：

如果单词以元音开头（'a', 'e', 'i', 'o', 'u'），在单词后添加"ma"。
- 例如，单词 "apple" 变为 "applema" 。
如果单词以辅音字母开头（即，非元音字母），移除第一个字符并将它放到末尾，之后再添加"ma"。
- 例如，单词 "goat" 变为 "oatgma" 。
根据单词在句子中的索引，在单词最后添加与索引相同数量的字母'a'，索引从 1 开始。
- 例如，在第一个单词后添加 "a" ，在第二个单词后添加 "aa" ，以此类推。

返回将 sentence 转换为山羊拉丁文后的句子。

示例 1：

输入：sentence = "I speak Goat Latin"
输出："Imaa peaksmaaa oatGmaaaa atinLmaaaaa"

示例 2：

输入：sentence = "The quick brown fox jumped over the lazy dog"
输出："heTmaa uickqmaaa rownbmaaaa oxfmaaaaa umpedjmaaaaaa overmaaaaaaa hetmaaaaaaaa azylmaaaaaaaaa ogdmaaaaaaaaaa"

提示：

1 <= sentence.length <= 150
sentence 由英文字母和空格组成
sentence 不含前导或尾随空格
sentence 中的所有单词由单个空格分隔

方法一：Go 解法（本站整理） · Go 实现

Doocs 参考题解 · CC BY-SA 4.0

本站根据题意与 Doocs 参考思路整理为 Go，非上游原文。按 CC BY-SA 4.0 共享。

按单词处理：若以辅音开头，将首字母移到末尾；随后添加 ma 和与单词序号相同数量的 a。元音判断同时接受大小写。设原文长 n、单词数 k，时间和输出空间为 O(n+k²)，因为新增 a 的数量本身是 k(k+1)/2。

import "strings"

func toGoatLatin(sentence string) string {
	words := strings.Fields(sentence)
	for i, w := range words {
		if !strings.ContainsRune("aeiouAEIOU", rune(w[0])) {
			w = w[1:] + w[:1]
		}
		words[i] = w + "ma" + strings.Repeat("a", i+1)
	}
	return strings.Join(words, " ")
}

力扣原题 · Doocs 题解来源

830. 较大分组的位置

简单1 种解法

标签：字符串

题目、示例与约束

在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。

例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。

示例 1：

输入：s = "abbxxxxzzy"
输出：[[3,6]]
解释："xxxx" 是一个起始于 3 且终止于 6 的较大分组。

示例 2：

输入：s = "abc"
输出：[]
解释："a","b" 和 "c" 均不是符合要求的较大分组。

示例 3：

输入：s = "abcdddeeeeaabbbcd"
输出：[[3,5],[6,9],[12,14]]
解释：较大分组为 "ddd", "eeee" 和 "bbb"

示例 4：

输入：s = "aba"
输出：[]

提示：

1 <= s.length <= 1000
s 仅含小写英文字母

方法一：双指针 · Go 实现

思考

大分组是长度至少为 $3$ 的连续相同字母段。串由小写字母组成，一次扫描找出所有这样的区间即可。

双指针圈定每一段，长度达到 $3$ 则记下起止下标，然后跳到下一段。

我们用双指针 $i$ 和 $j$ 找到每个分组的起始位置和终止位置，然后判断分组长度是否大于等于 $3$ ，若是则将其加入结果数组。

时间复杂度 $O (n)$ ，其中 $n$ 为字符串 $s$ 的长度。

func largeGroupPositions(s string) [][]int {
	i, n := 0, len(s)
	ans := [][]int{}
	for i < n {
		j := i
		for j < n && s[j] == s[i] {
			j++
		}
		if j-i >= 3 {
			ans = append(ans, []int{i, j - 1})
		}
		i = j
	}
	return ans
}

力扣原题 · Doocs 题解来源

831. 隐藏个人信息

中等1 种解法

标签：字符串

题目、示例与约束

给你一条个人信息字符串 s ，可能表示一个 邮箱地址 ，也可能表示一串 电话号码 。返回按如下规则隐藏个人信息后的结果：

电子邮件地址：

一个电子邮件地址由以下部分组成：

一个名字，由大小写英文字母组成，后面跟着
一个 '@' 字符，后面跟着
一个域名，由大小写英文字母和一个位于中间的 '.' 字符组成。'.' 不会是域名的第一个或者最后一个字符。

要想隐藏电子邮件地址中的个人信息：

名字和域名部分的大写英文字母应当转换成小写英文字母。
名字中间的字母（即，除第一个和最后一个字母外）必须用 5 个 "*****" 替换。

电话号码：

一个电话号码应当按下述格式组成：

电话号码可以由 10-13 位数字组成
后 10 位构成 本地号码
前面剩下的 0-3 位，构成 国家代码
利用 {'+', '-', '(', ')', ' '} 这些 分隔字符 按某种形式对上述数字进行分隔

要想隐藏电话号码中的个人信息：

移除所有 分隔字符
隐藏个人信息后的电话号码应该遵从这种格式：
- "***-***-XXXX" 如果国家代码为 0 位数字
- "+*-***-***-XXXX" 如果国家代码为 1 位数字
- "+**-***-***-XXXX" 如果国家代码为 2 位数字
- "+***-***-***-XXXX" 如果国家代码为 3 位数字
"XXXX" 是最后 4 位 本地号码

示例 1：

输入：s = "LeetCode@LeetCode.com"
输出："l*****e@leetcode.com"
解释：s 是一个电子邮件地址。
名字和域名都转换为小写，名字的中间用 5 个 * 替换。

示例 2：

输入：s = "AB@qq.com"
输出："a*****b@qq.com"
解释：s 是一个电子邮件地址。
名字和域名都转换为小写，名字的中间用 5 个 * 替换。
注意，尽管 "ab" 只有两个字符，但中间仍然必须有 5 个 * 。

示例 3：

输入：s = "1(234)567-890"
输出："***-***-7890"
解释：s 是一个电话号码。
共计 10 位数字，所以本地号码为 10 位数字，国家代码为 0 位数字。
因此，隐藏后的电话号码应该是 "***-***-7890" 。

提示：

s 是一个有效的电子邮件或者电话号码
如果 s 是一个电子邮件：
- 8 <= s.length <= 40
- s 是由大小写英文字母，恰好一个 '@' 字符，以及 '.' 字符组成
如果 s 是一个电话号码：
- 10 <= s.length <= 20
- s 是由数字、空格、字符 '('、')'、'-' 和 '+' 组成

方法一：模拟 · Go 实现

思考

输入保证是合法邮箱或电话，按第一种字符是否为字母分支处理即可，无需复杂解析。

邮箱转小写后保留首尾字母与域名；电话只留数字，按国家码位数决定是否加 +***- 前缀，本地号统一掩成后四位可见。

根据题目描述，我们可以先判断字符串 $s$ 是电子邮件还是电话号码，然后分别处理。

时间复杂度为 $O (n)$ ，空间复杂度为 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

func maskPII(s string) string {
	i := strings.Index(s, "@")
	if i != -1 {
		s = strings.ToLower(s)
		return s[0:1] + "*****" + s[i-1:]
	}
	t := []rune{}
	for _, c := range s {
		if c >= '0' && c <= '9' {
			t = append(t, c)
		}
	}
	s = string(t)
	cnt := len(s) - 10
	suf := "***-***-" + s[len(s)-4:]
	if cnt == 0 {
		return suf
	}
	return "+" + strings.Repeat("*", cnt) + "-" + suf
}

力扣原题 · Doocs 题解来源

944. 删列造序

简单1 种解法

标签：数组、字符串、最长上升子序列

题目、示例与约束

给你由 n 个小写字母字符串组成的数组 strs，其中每个字符串长度相等。

这些字符串可以每个一行，排成一个网格。例如，strs = ["abc", "bce", "cae"] 可以排列为：

abc
bce
cae

你需要找出并删除 不是按字典序非严格递增排列的 列。在上面的例子（下标从 0 开始）中，列 0（'a', 'b', 'c'）和列 2（'c', 'e', 'e'）都是按字典序非严格递增排列的，而列 1（'b', 'c', 'a'）不是，所以要删除列 1 。

返回你需要删除的列数。

示例 1：

输入：strs = ["cba","daf","ghi"]
输出：1
解释：网格示意如下：
  cba
  daf
  ghi
列 0 和列 2 按升序排列，但列 1 不是，所以只需要删除列 1 。

示例 2：

输入：strs = ["a","b"]
输出：0
解释：网格示意如下：
  a
  b
只有列 0 这一列，且已经按升序排列，所以不用删除任何列。

示例 3：

输入：strs = ["zyx","wvu","tsr"]
输出：3
解释：网格示意如下：
  zyx
  wvu
  tsr
所有 3 列都是非升序排列的，所以都要删除。

提示：

n == strs.length
1 <= n <= 100
1 <= strs[i].length <= 1000
strs[i] 由小写英文字母组成

方法一：逐列比较 · Go 实现

思考

删除最少列使每一列从上到下非降。列之间独立，一列只要存在相邻逆序就必须删。逐列比较相邻行，发现逆序即计数并处理下一列。

我们记字符串数组 $strs$ 的行数为 $n$ ，列数为 $m$ 。

遍历每一列，从第二行开始，逐列比较当前行和上一行的字符，如果当前行的字符小于上一行的字符，说明当前列不是按字典序非严格递增排列的，需要删除，结果加一，然后跳出内层循环。

最后返回结果即可。

时间复杂度 $O (L)$ ，其中 $L$ 为字符串数组 $strs$ 的长度。空间复杂度 $O (1)$ 。

func minDeletionSize(strs []string) (ans int) {
	m, n := len(strs[0]), len(strs)
	for j := 0; j < m; j++ {
		for i := 1; i < n; i++ {
			if strs[i][j] < strs[i-1][j] {
				ans++
				break
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 字符串（1） ​

6. Z 字形变换 ​

8. 字符串转换整数 (atoi) ​

38. 外观数列 ​

58. 最后一个单词的长度 ​

65. 有效数字 ​

68. 文本左右对齐 ​

214. 最短回文串 ​

243. 最短单词距离 🔒 ​

245. 最短单词距离 III 🔒 ​

247. 中心对称数 II 🔒 ​

248. 中心对称数 III 🔒 ​

293. 翻转游戏 🔒 ​

434. 字符串中的单词数 ​

459. 重复的子字符串 ​

468. 验证IP地址 ​

482. 密钥格式化 ​

520. 检测大写字母 ​

521. 最长特殊序列 Ⅰ ​

544. 输出比赛匹配对 🔒 ​

551. 学生出勤记录 I ​

657. 机器人能否返回原点 ​

686. 重复叠加字符串匹配 ​

709. 转换成小写字母 ​

722. 删除注释 ​

796. 旋转字符串 ​

806. 写字符串需要的行数 ​

824. 山羊拉丁文 ​

830. 较大分组的位置 ​

831. 隐藏个人信息 ​

944. 删列造序 ​

继续阅读

LeetCode Go · 字符串（1）

6. Z 字形变换

8. 字符串转换整数 (atoi)

38. 外观数列

58. 最后一个单词的长度

65. 有效数字

68. 文本左右对齐

214. 最短回文串

243. 最短单词距离 🔒

245. 最短单词距离 III 🔒

247. 中心对称数 II 🔒

248. 中心对称数 III 🔒

293. 翻转游戏 🔒

434. 字符串中的单词数

459. 重复的子字符串

468. 验证IP地址

482. 密钥格式化

520. 检测大写字母

521. 最长特殊序列 Ⅰ

544. 输出比赛匹配对 🔒

551. 学生出勤记录 I

657. 机器人能否返回原点

686. 重复叠加字符串匹配

709. 转换成小写字母

722. 删除注释

796. 旋转字符串

806. 写字符串需要的行数

824. 山羊拉丁文

830. 较大分组的位置

831. 隐藏个人信息

944. 删列造序