LeetCode Go · 字符串（3）

来源与许可

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

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

1945. 字符串转化后的各位数字之和

简单1 种解法

标签：字符串、模拟

题目、示例与约束

给你一个由小写字母组成的字符串 s ，以及一个整数 k 。你的任务是通过一种特殊处理将字符串转为整数，然后通过重复对它的数位求和 k 次来进行转换。更具体地说，执行以下步骤：

用字母在字母表中的位置替换该字母，将 s 转化为一个整数（也就是，'a' 用 1 替换，'b' 用 2 替换，... 'z' 用 26 替换）。
接着，将整数转换为其 各位数字之和 。
共重复转换操作（第 2 步） k 次。

例如，如果 s = "zbax" 且 k = 2 ，那么执行下述步骤后得到的结果是整数 8 ：

转化："zbax" ➝ "(26)(2)(1)(24)" ➝ "262124" ➝ 262124
转换 #1：262124 ➝ 2 + 6 + 2 + 1 + 2 + 4 ➝ 17
转换 #2：17 ➝ 1 + 7 ➝ 8

返回执行上述操作后得到的 结果整数。

示例 1：

输入：s = "iiii", k = 1

输出：36

解释：

操作如下：

转化："iiii" ➝ "(9)(9)(9)(9)" ➝ "9999" ➝ 9999
转换 #1：9999 ➝ 9 + 9 + 9 + 9 ➝ 36

因此，结果整数为 36 。

示例 2：

输入：s = "leetcode", k = 2

输出：6

解释：

操作如下：

转化："leetcode" ➝ "(12)(5)(5)(20)(3)(15)(4)(5)" ➝ "12552031545" ➝ 12552031545
转换 #1：12552031545 ➝ 1 + 2 + 5 + 5 + 2 + 0 + 3 + 1 + 5 + 4 + 5 ➝ 33
转换 #2：33 ➝ 3 + 3 ➝ 6

因此，结果整数为 6 。

示例 3：

输入：s = "zbax", k = 2

输出：8

提示：

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

方法一：模拟 · Go 实现

思考

先把字母换成位置数字再做 $k$ 次数位和。变换规则已给定，按描述模拟即可。

字母映射后字符串长度仍为 $O (n)$ ，随后每次数位和使值迅速变小，循环 $k$ 次后转回整数。

根据题目描述进行模拟即可。

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

func getLucky(s string, k int) int {
	var t strings.Builder
	for _, c := range s {
		t.WriteString(strconv.Itoa(int(c - 'a' + 1)))
	}
	s = t.String()
	for k > 0 {
		k--
		t := 0
		for _, c := range s {
			t += int(c - '0')
		}
		s = strconv.Itoa(t)
	}
	ans, _ := strconv.Atoi(s)
	return ans
}

力扣原题 · Doocs 题解来源

1957. 删除字符使字符串变好

简单1 种解法

标签：字符串

题目、示例与约束

一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。

给你一个字符串 s ，请你从 s 删除最少的字符，使它变成一个 好字符串 。

请你返回删除后的字符串。题目数据保证答案总是 唯一的 。

示例 1：

输入：s = "leeetcode"
输出："leetcode"
解释：
从第一组 'e' 里面删除一个 'e' ，得到 "leetcode" 。
没有连续三个相同字符，所以返回 "leetcode" 。

示例 2：

输入：s = "aaabaaaa"
输出："aabaa"
解释：
从第一组 'a' 里面删除一个 'a' ，得到 "aabaaaa" 。
从第二组 'a' 里面删除两个 'a' ，得到 "aabaa" 。
没有连续三个相同字符，所以返回 "aabaa" 。

示例 3：

输入：s = "aab"
输出："aab"
解释：没有连续三个相同字符，所以返回 "aab" 。

提示：

1 <= s.length <= 10⁵
s 只包含小写英文字母。

方法一：模拟 · Go 实现

思考

fancy 串不含连续三个相同字符，删除次数应尽可能少，等价于从左到右保留能留下的字符。

扫到 $s [i]$ 时，若它与前两个已保留字符不全相同则追加。这样每次只删必须删的那个，得到最长 fancy 串。

我们可以遍历字符串 $s$ ，并使用一个数组 $ans$ 记录当前的答案。对于每一个字符 $s[i]$ ，如果 $i < 2$ 或者 $s [i]$ 与 $s [i - 1]$ 不等，或者 $s [i]$ 与 $s [i - 2]$ 不等，我们就将 $s [i]$ 添加到 $ans$ 中。

最后，我们将 $ans$ 中的字符连接起来，就得到了答案。

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

func makeFancyString(s string) string {
	ans := []byte{}
	for i, ch := range s {
		if c := byte(ch); i < 2 || c != s[i-1] || c != s[i-2] {
			ans = append(ans, c)
		}
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

1967. 作为子字符串出现在单词中的字符串数目

简单1 种解法

标签：数组、字符串

题目、示例与约束

给你一个字符串数组 patterns 和一个字符串 word ，统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。

子字符串 是字符串中的一个连续字符序列。

示例 1：

输入：patterns = ["a","abc","bc","d"], word = "abc"
输出：3
解释：
- "a" 是 "abc" 的子字符串。
- "abc" 是 "abc" 的子字符串。
- "bc" 是 "abc" 的子字符串。
- "d" 不是 "abc" 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。

示例 2：

输入：patterns = ["a","b","c"], word = "aaaaabbbbb"
输出：2
解释：
- "a" 是 "aaaaabbbbb" 的子字符串。
- "b" 是 "aaaaabbbbb" 的子字符串。
- "c" 不是 "aaaaabbbbb" 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。

示例 3：

输入：patterns = ["a","a","a"], word = "ab"
输出：3
解释：patterns 中的每个字符串都作为子字符串出现在 word "ab" 中。

提示：

1 <= patterns.length <= 100
1 <= patterns[i].length <= 100
1 <= word.length <= 100
patterns[i] 和 word 由小写英文字母组成

方法一：模拟 · Go 实现

思考

模式串与文本都较短，直接判断 $p$ 是否为 $word$ 的子串并计数即可，无需自动机。

遍历字符串数组 $patterns$ 中的每个字符串 $p$ ，判断其是否为 $word$ 的子字符串，如果是，答案加一。

遍历结束后，返回答案。

时间复杂度 $O (n \times m)$ ，空间复杂度 $O (1)$ 。其中 $n$ 和 $m$ 分别为 $patterns$ 和 $word$ 的长度。

func numOfStrings(patterns []string, word string) (ans int) {
	for _, p := range patterns {
		if strings.Contains(word, p) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2011. 执行操作后的变量值

简单1 种解法

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

题目、示例与约束

存在一种仅支持 4 种操作和 1 个变量 X 的编程语言：

++X 和 X++ 使变量 X 的值加 1
--X 和 X-- 使变量 X 的值减 1

最初，X 的值是 0

给你一个字符串数组 operations ，这是由操作组成的一个列表，返回执行所有操作后， X 的 最终值 。

示例 1：

输入：operations = ["--X","X++","X++"]
输出：1
解释：操作按下述步骤执行：
最初，X = 0
--X：X 减 1 ，X =  0 - 1 = -1
X++：X 加 1 ，X = -1 + 1 =  0
X++：X 加 1 ，X =  0 + 1 =  1

示例 2：

输入：operations = ["++X","++X","X++"]
输出：3
解释：操作按下述步骤执行： 
最初，X = 0
++X：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
X++：X 加 1 ，X = 2 + 1 = 3

示例 3：

输入：operations = ["X++","++X","--X","X--"]
输出：0
解释：操作按下述步骤执行：
最初，X = 0
X++：X 加 1 ，X = 0 + 1 = 1
++X：X 加 1 ，X = 1 + 1 = 2
--X：X 减 1 ，X = 2 - 1 = 1
X--：X 减 1 ，X = 1 - 1 = 0

提示：

1 <= operations.length <= 100
operations[i] 将会是 "++X"、"X++"、"--X" 或 "X--"

方法一：计数 · Go 实现

思考

操作仅四种，且 $n \leq 100$ ，顺序模拟即可。++X 与 X++ 都使变量加一，--X 与 X-- 都减一，真正起作用的是中间那个字符。

因此对每个串看 $s [1]$ 是否为 '+'，将 $+ 1$ 或 $- 1$ 求和。

我们遍历数组 $operations$ ，对于每个操作 $operations [i]$ ，如果包含 '+'，那么答案加 $1$ ，否则答案减 $1$ 。

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

func finalValueAfterOperations(operations []string) (ans int) {
	for _, s := range operations {
		if s[1] == '+' {
			ans += 1
		} else {
			ans -= 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2042. 检查句子中的数字是否递增

简单1 种解法

标签：字符串

题目、示例与约束

句子是由若干 token 组成的一个列表，token 间用单个空格分隔，句子没有前导或尾随空格。每个 token 要么是一个由数字 0-9 组成的不含前导零的 正整数 ，要么是一个由小写英文字母组成的单词。

示例，"a puppy has 2 eyes 4 legs" 是一个由 7 个 token 组成的句子："2" 和 "4" 是数字，其他像 "puppy" 这样的 tokens 属于单词。

给你一个表示句子的字符串 s ，你需要检查 s 中的全部数字是否从左到右严格递增（即，除了最后一个数字，s 中的每个数字都严格小于它右侧的数字）。

如果满足题目要求，返回 true ，否则，返回 false 。

示例 1：

example-1

输入：s = "1 box has 3 blue 4 red 6 green and 12 yellow marbles"
输出：true
解释：句子中的数字是：1, 3, 4, 6, 12 。
这些数字是按从左到右严格递增的 1 < 3 < 4 < 6 < 12 。

示例 2：

输入：s = "hello world 5 x 5"
输出：false
解释：句子中的数字是：5, 5 。这些数字不是严格递增的。

示例 3：

example-3

输入：s = "sunset is at 7 51 pm overnight lows will be in the low 50 and 60 s"
输出：false
解释：s 中的数字是：7, 51, 50, 60 。这些数字不是严格递增的。

示例 4：

输入：s = "4 5 11 26"
输出：true
解释：s 中的数字是：4, 5, 11, 26 。
这些数字是按从左到右严格递增的：4 < 5 < 11 < 26 。

提示：

3 <= s.length <= 200
s 由小写英文字母、空格和数字 0 到 9 组成（包含 0 和 9）
s 中数字 token 的数目在 2 和 100 之间（包含 2 和 100）
s 中的 token 之间由单个空格分隔
s 中至少有两个数字
s 中的每个数字都是一个小于 100 的正数，且不含前导零
s 不含前导或尾随空格

方法一：模拟 · Go 实现

思考

句子长度 $\leq 200$ ，按空格拆出 token 后只需检查数字是否严格递增。非数字 token 忽略。

维护上一个数字 $p r e$ ，当前数字 $\leq p r e$ 则失败。全部通过则成功。

我们可以将字符串 $s$ 按空格分割成若干个单词。然后遍历每个单词，判断其是否为数字，若是数字，则将其转换为整数，与前一个数字比较，若不严格递增，返回 false，否则，将当前数字赋值给前一个数字，继续遍历。

遍历结束，说明字符串中的数字严格递增，返回 true。

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

func areNumbersAscending(s string) bool {
	pre := 0
	for _, t := range strings.Split(s, " ") {
		if t[0] <= '9' {
			cur, _ := strconv.Atoi(t)
			if pre >= cur {
				return false
			}
			pre = cur
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2047. 句子中的有效单词数

简单1 种解法

标签：字符串

题目、示例与约束

句子仅由小写字母（'a' 到 'z'）、数字（'0' 到 '9'）、连字符（'-'）、标点符号（'!'、'.' 和 ','）以及空格（' '）组成。每个句子可以根据空格分解成 一个或者多个 token ，这些 token 之间由一个或者多个空格 ' ' 分隔。

如果一个 token 同时满足下述条件，则认为这个 token 是一个有效单词：

仅由小写字母、连字符和/或标点（不含数字）组成。
至多一个 连字符 '-' 。如果存在，连字符两侧应当都存在小写字母（"a-b" 是一个有效单词，但 "-ab" 和 "ab-" 不是有效单词）。
至多一个 标点符号。如果存在，标点符号应当位于 token 的末尾。

这里给出几个有效单词的例子："a-b."、"afad"、"ba-c"、"a!" 和 "!" 。

给你一个字符串 sentence ，请你找出并返回 sentence 中 有效单词的数目 。

示例 1：

输入：sentence = "cat and  dog"
输出：3
解释：句子中的有效单词是 "cat"、"and" 和 "dog"

示例 2：

输入：sentence = "!this  1-s b8d!"
输出：0
解释：句子中没有有效单词
"!this" 不是有效单词，因为它以一个标点开头
"1-s" 和 "b8d" 也不是有效单词，因为它们都包含数字

示例 3：

输入：sentence = "alice and  bob are playing stone-game10"
输出：5
解释：句子中的有效单词是 "alice"、"and"、"bob"、"are" 和 "playing"
"stone-game10" 不是有效单词，因为它含有数字

提示：

1 <= sentence.length <= 1000
sentence 由小写英文字母、数字（0-9）、以及字符（' '、'-'、'!'、'.' 和 ','）组成
句子中至少有 1 个 token

方法一：模拟 · Go 实现

思考

句子长度 $\leq 1000$ ，按空格拆词后逐词检查规则：无数字、标点只在末尾、连字符至多一个且两侧为字母。

用布尔量记录是否已出现连字符，扫描每个字符按题面约束判定。对拆出的 token 计数即可。

我们首先将句子按空格分割成单词，然后对每个单词进行检查，判断是否为有效单词。

对于每个单词，我们可以使用一个布尔变量 $st$ 来记录是否已经出现过连字符，然后遍历单词中的每个字符，根据题目描述的规则进行判断。

对于每个字符 $s [i]$ ，我们有以下几种情况：

如果 $s [i]$ 是数字，那么 $s$ 不是有效单词，直接返回 $false$ ；
如果 $s [i]$ 是标点符号（'!'、'.'、','）且 $i < len (s) - 1$ ，那么 $s$ 不是有效单词，直接返回 $false$ ；
如果 $s [i]$ 是连字符，那么我们需要判断是否满足以下条件：
- 连字符只能出现一次；
- 连字符不能出现在单词的开头或结尾；
- 连字符两侧必须是字母；
如果 $s [i]$ 是字母，那么我们不需要做任何处理。

最后，我们统计出句子中的有效单词数即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是句子的长度。

func countValidWords(sentence string) (ans int) {
	check := func(s string) int {
		if len(s) == 0 {
			return 0
		}
		st := false
		for i, r := range s {
			if unicode.IsDigit(r) {
				return 0
			}
			if (r == '!' || r == '.' || r == ',') && i < len(s)-1 {
				return 0
			}
			if r == '-' {
				if st || i == 0 || i == len(s)-1 {
					return 0
				}
				if !unicode.IsLetter(rune(s[i-1])) || !unicode.IsLetter(rune(s[i+1])) {
					return 0
				}
				st = true
			}
		}
		return 1
	}
	for _, s := range strings.Fields(sentence) {
		ans += check(s)
	}
	return ans
}

力扣原题 · Doocs 题解来源

2075. 解码斜向换位密码

中等1 种解法

标签：字符串、模拟

题目、示例与约束

字符串 originalText 使用 斜向换位密码 ，经由 行数固定 为 rows 的矩阵辅助，加密得到一个字符串 encodedText 。

originalText 先按从左上到右下的方式放置到矩阵中。

先填充蓝色单元格，接着是红色单元格，然后是黄色单元格，以此类推，直到到达 originalText 末尾。箭头指示顺序即为单元格填充顺序。所有空单元格用 ' ' 进行填充。矩阵的列数需满足：用 originalText 填充之后，最右侧列 不为空 。

接着按行将字符附加到矩阵中，构造 encodedText 。

先把蓝色单元格中的字符附加到 encodedText 中，接着是红色单元格，最后是黄色单元格。箭头指示单元格访问顺序。

例如，如果 originalText = "cipher" 且 rows = 3 ，那么我们可以按下述方法将其编码：

蓝色箭头标识 originalText 是如何放入矩阵中的，红色箭头标识形成 encodedText 的顺序。在上述例子中，encodedText = "ch ie pr" 。

给你编码后的字符串 encodedText 和矩阵的行数 rows ，返回源字符串 originalText 。

注意：originalText 不含任何尾随空格 ' ' 。生成的测试用例满足 仅存在一个 可能的 originalText 。

示例 1：

输入：encodedText = "ch   ie   pr", rows = 3
输出："cipher"
解释：此示例与问题描述中的例子相同。

示例 2：

输入：encodedText = "iveo    eed   l te   olc", rows = 4
输出："i love leetcode"
解释：上图标识用于编码 originalText 的矩阵。 
蓝色箭头展示如何从 encodedText 找到 originalText 。

示例 3：

输入：encodedText = "coding", rows = 1
输出："coding"
解释：由于只有 1 行，所以 originalText 和 encodedText 是相同的。

示例 4：

输入：encodedText = " b  ac", rows = 2
输出：" abc"
解释：originalText 不能含尾随空格，但它可能会有一个或者多个前置空格。

提示：

0 <= encodedText.length <= 10⁶
encodedText 仅由小写英文字母和 ' ' 组成
encodedText 是对某个不含尾随空格的 originalText 的一个有效编码
1 <= rows <= 1000
生成的测试用例满足 仅存在一个 可能的 originalText

方法一：模拟 · Go 实现

思考

密文按行填入矩阵后再沿对角线读出。已知行数则可还原列数，按对角线模拟即可。 $n \leq 10^{6}$ ，每个字符访问一次。

从每一列顶出发向右下走，追加字符，最后去掉题面保证的尾随空格。

我们先计算出矩阵的列数 $c o l s = len (e n c o d e d T e x t) / r o w s$ ，然后按照题目描述的规则，从左上角开始遍历矩阵，将字符添加到答案中。

最后返回答案，注意去掉末尾的空格。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $e n c o d e d T e x t$ 的长度。

func decodeCiphertext(encodedText string, rows int) string {
	ans := []byte{}
	cols := len(encodedText) / rows
	for j := 0; j < cols; j++ {
		for x, y := 0, j; x < rows && y < cols; x, y = x+1, y+1 {
			ans = append(ans, encodedText[x*cols+y])
		}
	}
	for len(ans) > 0 && ans[len(ans)-1] == ' ' {
		ans = ans[:len(ans)-1]
	}
	return string(ans)
}

力扣原题 · Doocs 题解来源

2114. 句子中的最多单词数

简单1 种解法

标签：数组、字符串

题目、示例与约束

一个句子由一些单词以及它们之间的单个空格组成，句子的开头和结尾不会有多余空格。

给你一个字符串数组 sentences ，其中 sentences[i] 表示单个句子。

请你返回单个句子里 单词的最多数目 。

示例 1：

输入：sentences = ["alice and bob love leetcode", "i think so too", "this is great thanks very much"]
输出：6
解释：
- 第一个句子 "alice and bob love leetcode" 总共有 5 个单词。
- 第二个句子 "i think so too" 总共有 4 个单词。
- 第三个句子 "this is great thanks very much" 总共有 6 个单词。
所以，单个句子中有最多单词数的是第三个句子，总共有 6 个单词。

示例 2：

输入：sentences = ["please wait", "continue to fight", "continue to win"]
输出：3
解释：可能有多个句子有相同单词数。
这个例子中，第二个句子和第三个句子（加粗斜体）有相同数目的单词数。

提示：

1 <= sentences.length <= 100
1 <= sentences[i].length <= 100
sentences[i] 只包含小写英文字母和 ' ' 。
sentences[i] 的开头和结尾都没有空格。
sentences[i] 中所有单词由单个空格隔开。

方法一：空格计数 · Go 实现

思考

一句中的单词由空格分隔，单词数等于空格数加一。句子总长有限，逐句统计空格即可。

无需分词成列表，对每个句子调用计数后取最大值。

答案为 $1 + max_{s} s . count (’ ’)$ 。

我们遍历数组 sentences，对于每个句子，我们计算其中的空格数，那么单词数就是空格数加 $1$ 。最后返回最大的单词数即可。

时间复杂度 $O (L)$ ，其中 $L$ 是数组 sentences 中所有字符串的长度之和。空间复杂度 $O (1)$ 。

func mostWordsFound(sentences []string) (ans int) {
	for _, s := range sentences {
		cnt := 1 + strings.Count(s, " ")
		if ans < cnt {
			ans = cnt
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2120. 执行所有后缀指令

中等1 种解法

标签：字符串、模拟

题目、示例与约束

现有一个 n x n 大小的网格，左上角单元格坐标 (0, 0) ，右下角单元格坐标 (n - 1, n - 1) 。给你整数 n 和一个整数数组 startPos ，其中 startPos = [start_row, start_col] 表示机器人最开始在坐标为 (start_row, start_col) 的单元格上。

另给你一个长度为 m 、下标从 0 开始的字符串 s ，其中 s[i] 是对机器人的第 i 条指令：'L'（向左移动），'R'（向右移动），'U'（向上移动）和 'D'（向下移动）。

机器人可以从 s 中的任一第 i 条指令开始执行。它将会逐条执行指令直到 s 的末尾，但在满足下述条件之一时，机器人将会停止：

下一条指令将会导致机器人移动到网格外。
没有指令可以执行。

返回一个长度为 m 的数组 answer ，其中 answer[i] 是机器人从第 i 条指令开始，可以执行的 指令数目 。

示例 1：

输入：n = 3, startPos = [0,1], s = "RRDDLU"
输出：[1,5,4,3,1,0]
解释：机器人从 startPos 出发，并从第 i 条指令开始执行：
- 0: "RRDDLU" 在移动到网格外之前，只能执行一条 "R" 指令。
- 1:  "RDDLU" 可以执行全部五条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 2:   "DDLU" 可以执行全部四条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 3:    "DLU" 可以执行全部三条指令，机器人仍在网格内，最终到达 (0, 0) 。
- 4:     "LU" 在移动到网格外之前，只能执行一条 "L" 指令。
- 5:      "U" 如果向上移动，将会移动到网格外。

示例 2：

输入：n = 2, startPos = [1,1], s = "LURD"
输出：[4,1,0,0]
解释：
- 0: "LURD"
- 1:  "URD"
- 2:   "RD"
- 3:    "D"

示例 3：

输入：n = 1, startPos = [0,0], s = "LRUD"
输出：[0,0,0,0]
解释：无论机器人从哪条指令开始执行，都会移动到网格外。

提示：

m == s.length
1 <= n, m <= 500
startPos.length == 2
0 <= start_row, start_col < n
s 由 'L'、'R'、'U' 和 'D' 组成

方法一 · Go 实现

思考

对每个起始下标 $i$ ，需要从 $startPos$ 执行指令后缀 $s [i :]$ ，直到越界或指令用尽，统计步数。指令长 $m \leq 500$ ，对每个 $i$ 模拟剩余指令的总代价为 $O (m^{2})$ ，可以接受。

格子有界，每一步由字符决定位移，越界即停。不同后缀的起点相同但路径不同，难以共享状态，直接双重循环即可。

外层枚举起点 $i$ ，内层从 $i$ 走到末尾并更新坐标，累加合法步数。

func executeInstructions(n int, startPos []int, s string) []int {
	m := len(s)
	mp := make(map[byte][]int)
	mp['L'] = []int{0, -1}
	mp['R'] = []int{0, 1}
	mp['U'] = []int{-1, 0}
	mp['D'] = []int{1, 0}
	ans := make([]int, m)
	for i := 0; i < m; i++ {
		x, y := startPos[0], startPos[1]
		t := 0
		for j := i; j < m; j++ {
			a, b := mp[s[j]][0], mp[s[j]][1]
			if 0 <= x+a && x+a < n && 0 <= y+b && y+b < n {
				x += a
				y += b
				t++
			} else {
				break
			}
		}
		ans[i] = t
	}
	return ans
}

力扣原题 · Doocs 题解来源

2124. 检查是否所有 A 都在 B 之前

简单1 种解法

标签：字符串

题目、示例与约束

给你一个仅由字符 'a' 和 'b' 组成的字符串 s 。如果字符串中每个 'a' 都出现在每个 'b' 之前，返回 true ；否则，返回 false 。

示例 1：

输入：s = "aaabbb"
输出：true
解释：
'a' 位于下标 0、1 和 2 ；而 'b' 位于下标 3、4 和 5 。
因此，每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

示例 2：

输入：s = "abab"
输出：false
解释：
存在一个 'a' 位于下标 2 ，而一个 'b' 位于下标 1 。
因此，不能满足每个 'a' 都出现在每个 'b' 之前，所以返回 false 。

示例 3：

输入：s = "bbb"
输出：true
解释：
不存在 'a' ，因此可以视作每个 'a' 都出现在每个 'b' 之前，所以返回 true 。

提示：

1 <= s.length <= 100
s[i] 为 'a' 或 'b'

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

思考

串只含 a 与 b，所有 a 都在所有 b 之前，当且仅当不存在某个 b 后面还出现 a，也即不出现子串 ba。

线性扫描或直接做子串判定即可在 $O (n)$ 内得出结论。

因此返回 "ba" 是否不在 $s$ 中。

根据题意，字符串 $s$ 仅由字符 a, b 组成。

要使得所有 a 都在 b 之前出现，需要满足 b 之后不会出现 a，也就是说，字符串 "ba" 不是字符串 $s$ 的子串，条件才能成立。

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

func checkString(s string) bool {
	return !strings.Contains(s, "ba")
}

力扣原题 · Doocs 题解来源

2129. 将标题首字母大写

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 title ，它由单个空格连接一个或多个单词组成，每个单词都只包含英文字母。请你按以下规则将每个单词的首字母大写：

如果单词的长度为 1 或者 2 ，所有字母变成小写。
否则，将单词首字母大写，剩余字母变成小写。

请你返回 大写后 的 title 。

示例 1：

输入：title = "capiTalIze tHe titLe"
输出："Capitalize The Title"
解释：
由于所有单词的长度都至少为 3 ，将每个单词首字母大写，剩余字母变为小写。

示例 2：

输入：title = "First leTTeR of EACH Word"
输出："First Letter of Each Word"
解释：
单词 "of" 长度为 2 ，所以它保持完全小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

示例 3：

输入：title = "i lOve leetcode"
输出："i Love Leetcode"
解释：
单词 "i" 长度为 1 ，所以它保留小写。
其他单词长度都至少为 3 ，所以其他单词首字母大写，剩余字母小写。

提示：

1 <= title.length <= 100
title 由单个空格隔开的单词组成，且不含有任何前导或后缀空格。
每个单词由大写和小写英文字母组成，且都是非空的。

方法一：模拟 · Go 实现

思考

按空格分词后，长度小于 $3$ 的单词全小写，其余仅首字母大写。规则对每个单词独立，模拟即可。

先统一 $lower$ ，再对长词 $capitalize$ ，最后用空格拼接。

复杂度与标题长度成线性。

直接模拟，按空格切分字符串，得到每个单词，再按题目转大小写。最后用空格连接每个单词。

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

func capitalizeTitle(title string) string {
	title = strings.ToLower(title)
	words := strings.Split(title, " ")
	for i, s := range words {
		if len(s) > 2 {
			words[i] = strings.Title(s)
		}
	}
	return strings.Join(words, " ")
}

力扣原题 · Doocs 题解来源

2138. 将字符串拆分为若干长度为 k 的组

简单1 种解法

标签：字符串、模拟

题目、示例与约束

字符串 s 可以按下述步骤划分为若干长度为 k 的组：

第一组由字符串中的前 k 个字符组成，第二组由接下来的 k 个字符串组成，依此类推。每个字符都能够成为 某一个 组的一部分。
对于最后一组，如果字符串剩下的字符不足 k 个，需使用字符 fill 来补全这一组字符。

注意，在去除最后一个组的填充字符 fill（如果存在的话）并按顺序连接所有的组后，所得到的字符串应该是 s 。

给你一个字符串 s ，以及每组的长度 k 和一个用于填充的字符 fill ，按上述步骤处理之后，返回一个字符串数组，该数组表示 s 分组后 每个组的组成情况 。

示例 1：

输入：s = "abcdefghi", k = 3, fill = 'x'
输出：["abc","def","ghi"]
解释：
前 3 个字符是 "abc" ，形成第一组。
接下来 3 个字符是 "def" ，形成第二组。
最后 3 个字符是 "ghi" ，形成第三组。
由于所有组都可以由字符串中的字符完全填充，所以不需要使用填充字符。
因此，形成 3 组，分别是 "abc"、"def" 和 "ghi" 。

示例 2：

输入：s = "abcdefghij", k = 3, fill = 'x'
输出：["abc","def","ghi","jxx"]
解释：
与前一个例子类似，形成前三组 "abc"、"def" 和 "ghi" 。
对于最后一组，字符串中仅剩下字符 'j' 可以用。为了补全这一组，使用填充字符 'x' 两次。
因此，形成 4 组，分别是 "abc"、"def"、"ghi" 和 "jxx" 。

提示：

1 <= s.length <= 100
s 仅由小写英文字母组成
1 <= k <= 100
fill 是一个小写英文字母

方法一：模拟 · Go 实现

思考

按长度 $k$ 切分字符串，最后一组不足则用 $fill$ 补齐。规则明确，模拟即可。

步长为 $k$ 取切片，再用 $ljust$ 填充。

结果列表长度约为 $n / k$ 。

我们可以直接模拟题目描述的过程，将字符串 $s$ 按照长度 $k$ 进行分组，然后对于最后一组不足 $k$ 个字符的情况，使用字符 $fill$ 进行填充。

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

func divideString(s string, k int, fill byte) (ans []string) {
	n := len(s)
	if n%k != 0 {
		s += strings.Repeat(string(fill), k-n%k)
	}
	for i := 0; i < len(s)/k; i++ {
		ans = append(ans, s[i*k:(i+1)*k])
	}
	return
}

力扣原题 · Doocs 题解来源

2185. 统计包含给定前缀的字符串

简单2 种解法

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

题目、示例与约束

给你一个字符串数组 words 和一个字符串 pref 。

返回 words 中以 pref 作为前缀的字符串的数目。

字符串 s 的前缀就是 s 的任一前导连续字符串。

示例 1：

输入：words = ["pay","attention","practice","attend"], pref = "at"
输出：2
解释：以 "at" 作为前缀的字符串有两个，分别是："attention" 和 "attend" 。

示例 2：

输入：words = ["leetcode","win","loops","success"], pref = "code"
输出：0
解释：不存在以 "code" 作为前缀的字符串。

提示：

1 <= words.length <= 100
1 <= words[i].length, pref.length <= 100
words[i] 和 pref 由小写英文字母组成

方法一：一次遍历 · Go 实现

思考

统计以 $pref$ 开头的单词个数。单词数量与长度都不大，对每个词做前缀判断即可。

$startswith$ 比较至多 $| pref |$ 个字符。

答案为真值之和。

根据题目描述，我们遍历字符串数组 words 中的每个字符串 $w$ ，判断其是否以 $p r e f$ 作为前缀，如果是，则答案加一。

时间复杂度 $O (n \times m)$ ，空间复杂度 $O (1)$ 。其中 $n$ 和 $m$ 分别是字符串数组 words 和字符串 $p r e f$ 的长度。

func prefixCount(words []string, pref string) (ans int) {
	for _, w := range words {
		if strings.HasPrefix(w, pref) {
			ans++
		}
	}
	return
}

方法二：前缀树 · Go 实现

思考

方法一已线性扫过所有字符。若同一词表上还有多次前缀询问，可先建字典树，把前缀计数存在结点上。

插入时沿路径增加 $cnt$ ，查询则走到 $pref$ 对应结点读取 $cnt$ ，中途缺失则返回 $0$ 。

本题只有一次查询，字典树作为可扩展的第二种写法。

我们还可以使用前缀树来查询答案。

定义前缀树的每个节点结构如下：

children：长度为 $26$ 的数组，用于存储当前节点的所有子节点，其中 children[i] 表示当前节点的子节点；
cnt：所有以当前节点为前缀的字符串的数量。

另外，我们还需要定义两个函数：

其中一个函数 $i n s e r t (w)$ 用于将字符串 $w$ 插入前缀树中；
另一个函数 $s e a r c h (p r e f)$ 用于查询以字符串 $p r e f$ 作为前缀的字符串的数量。查询时，我们从前缀树的根节点开始，遍历字符串 $p r e f$ ，如果当前节点的子节点中不存在 $p r e f [i]$ ，则说明 $p r e f$ 不是任何字符串的前缀，直接返回 $0$ 。否则，我们继续遍历 $p r e f$ 的下一个字符，直到遍历完 $p r e f$ ，返回当前节点的 cnt 即可。

有了上述函数，我们就可以查询答案了。

遍历字符串数组 words，对于每个字符串 $w$ ，调用 $i n s e r t (w)$ 函数将其插入前缀树中。最后调用 $s e a r c h (p r e f)$ 函数作为答案返回即可。

时间复杂度 $O (L)$ ，空间复杂度 $O (L)$ 。其中 $L$ 是字符串数组 words 中所有字符串的长度之和。

type Trie struct {
	children [26]*Trie
	cnt      int
}

func newTrie() *Trie {
	return &Trie{}
}

func (this *Trie) insert(w string) {
	node := this
	for _, c := range w {
		c -= 'a'
		if node.children[c] == nil {
			node.children[c] = newTrie()
		}
		node = node.children[c]
		node.cnt++
	}
}

func (this *Trie) search(pref string) int {
	node := this
	for _, c := range pref {
		c -= 'a'
		if node.children[c] == nil {
			return 0
		}
		node = node.children[c]
	}
	return node.cnt
}

func prefixCount(words []string, pref string) int {
	tree := newTrie()
	for _, w := range words {
		tree.insert(w)
	}
	return tree.search(pref)
}

力扣原题 · Doocs 题解来源

2194. Excel 表中某个范围内的单元格

简单1 种解法

标签：字符串

题目、示例与约束

Excel 表中的一个单元格 (r, c) 会以字符串 "<col><row>" 的形式进行表示，其中：

<col> 即单元格的列号 c 。用英文字母表中的字母标识。
- 例如，第 1 列用 'A' 表示，第 2 列用 'B' 表示，第 3 列用 'C' 表示，以此类推。
<row> 即单元格的行号 r 。第 r 行就用整数 r 标识。

给你一个格式为 "<col1><row1>:<col2><row2>" 的字符串 s ，其中 <col1> 表示 c1 列，<row1> 表示 r1 行，<col2> 表示 c2 列，<row2> 表示 r2 行，并满足 r1 <= r2 且 c1 <= c2 。

找出所有满足 r1 <= x <= r2 且 c1 <= y <= c2 的单元格，并以列表形式返回。单元格应该按前面描述的格式用 字符串 表示，并以 非递减 顺序排列（先按列排，再按行排）。

示例 1：

输入：s = "K1:L2"
输出：["K1","K2","L1","L2"]
解释：
上图显示了列表中应该出现的单元格。
红色箭头指示单元格的出现顺序。

示例 2：

输入：s = "A1:F1"
输出：["A1","B1","C1","D1","E1","F1"]
解释：
上图显示了列表中应该出现的单元格。 
红色箭头指示单元格的出现顺序。

提示：

s.length == 5
'A' <= s[0] <= s[3] <= 'Z'
'1' <= s[1] <= s[4] <= '9'
s 由大写英文字母、数字、和 ':' 组成

方法一：模拟 · Go 实现

思考

给定形如 A1:F2 的矩形，按列优先再按行列出单元格。列与行范围都很小，双重循环即可。

外层枚举列字符，内层枚举行号，拼接成字符串。

起止列取 $s$ 的首尾字母，起止行取两端数字。

我们直接遍历范围内的所有单元格，将其添加到答案数组中。

时间复杂度 $O (m \times n)$ ，空间复杂度 $O (m \times n)$ ，其中 $m$ 和 $n$ 分别为行数和列数的取值范围。

func cellsInRange(s string) (ans []string) {
	for i := s[0]; i <= s[3]; i++ {
		for j := s[1]; j <= s[4]; j++ {
			ans = append(ans, string(i)+string(j))
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2232. 向表达式添加括号后的最小结果

中等1 种解法

标签：字符串、枚举

题目、示例与约束

给你一个下标从 0 开始的字符串 expression ，格式为 "<num1>+<num2>" ，其中 <num1> 和 <num2> 表示正整数。

请你向 expression 中添加一对括号，使得在添加之后， expression 仍然是一个有效的数学表达式，并且计算后可以得到最小可能值。左括号必须添加在 '+' 的左侧，而右括号必须添加在 '+' 的右侧。

返回添加一对括号后形成的表达式 expression ，且满足 expression 计算得到最小可能值。如果存在多个答案都能产生相同结果，返回任意一个答案。

生成的输入满足：expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围。

示例 1：

输入：expression = "247+38"
输出："2(47+38)"
解释：表达式计算得到 2 * (47 + 38) = 2 * 85 = 170 。
注意 "2(4)7+38" 不是有效的结果，因为右括号必须添加在 '+' 的右侧。
可以证明 170 是最小可能值。

示例 2：

输入：expression = "12+34"
输出："1(2+3)4"
解释：表达式计算得到 1 * (2 + 3) * 4 = 1 * 5 * 4 = 20 。

示例 3：

输入：expression = "999+999"
输出："(999+999)"
解释：表达式计算得到 999 + 999 = 1998 。

提示：

3 <= expression.length <= 10
expression 仅由数字 '1' 到 '9' 和 '+' 组成
expression 由数字开始和结束
expression 恰好仅含有一个 '+'.
expression 的原始值和添加满足要求的任一对括号之后 expression 的值，都符合 32-bit 带符号整数范围

方法一：Go 实现（灵茶山艾府） · Go 实现

灵茶山艾府 · 源码 · MIT 许可

本站根据 Go 源码整理，非作者原文。

思路：在加号左侧枚举左括号位置，在右侧枚举右括号位置，保证括号中包含加号及两边至少一个数字。把表达式拆为 a×(b+c)×d，括号外为空时对应因子取 1，逐一计算并在结果更小时重建答案字符串。

复杂度：设加号两侧长度分别为 p、q，总数字长度为 N=p+q。共有 pq 种括号位置，但源码会反复用 Atoi 解析子串，并在更新答案时构造长度 O(N) 的字符串；计入这些操作，时间上界为 O(pq(p+q))，也即 O(N³) 上界，峰值空间为 O(N)，包含结果字符串。

import (
	"fmt"
	"math"
	"strconv"
	"strings"
)

// github.com/EndlessCheng/codeforces-go
func minimizeResult(expression string) (ans string) {
	sp := strings.Split(expression, "+")
	l, r := sp[0], sp[1]
	for i, min := 0, math.MaxInt64; i < len(l); i++ {
		a := 1
		if i > 0 {
			a, _ = strconv.Atoi(l[:i])
		}
		b, _ := strconv.Atoi(l[i:])
		for j := 1; j <= len(r); j++ {
			c, _ := strconv.Atoi(r[:j])
			d := 1
			if j < len(r) {
				d, _ = strconv.Atoi(r[j:])
			}
			res := a * (b + c) * d
			if res < min {
				min = res
				ans = fmt.Sprintf("%s(%s+%s)%s", l[:i], l[i:], r[:j], r[j:])
			}
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2243. 计算字符串的数字和

简单1 种解法

标签：字符串、模拟

题目、示例与约束

给你一个由若干数字（0 - 9）组成的字符串 s ，和一个整数。

如果 s 的长度大于 k ，则可以执行一轮操作。在一轮操作中，需要完成以下工作：

将 s 拆分成长度为 k 的若干 连续数字组 ，使得前 k 个字符都分在第一组，接下来的 k 个字符都分在第二组，依此类推。注意，最后一个数字组的长度可以小于 k 。
用表示每个数字组中所有数字之和的字符串来替换对应的数字组。例如，"346" 会替换为 "13" ，因为 3 + 4 + 6 = 13 。
合并所有组以形成一个新字符串。如果新字符串的长度大于 k 则重复第一步。

返回在完成所有轮操作后的 s 。

示例 1：

输入：s = "11111222223", k = 3
输出："135"
解释：
- 第一轮，将 s 分成："111"、"112"、"222" 和 "23" 。
  接着，计算每一组的数字和：1 + 1 + 1 = 3、1 + 1 + 2 = 4、2 + 2 + 2 = 6 和 2 + 3 = 5 。 
  这样，s 在第一轮之后变成 "3" + "4" + "6" + "5" = "3465" 。
- 第二轮，将 s 分成："346" 和 "5" 。
  接着，计算每一组的数字和：3 + 4 + 6 = 13 、5 = 5 。
  这样，s 在第二轮之后变成 "13" + "5" = "135" 。 
现在，s.length <= k ，所以返回 "135" 作为答案。

示例 2：

输入：s = "00000000", k = 3
输出："000"
解释：
将 "000", "000", and "00".
接着，计算每一组的数字和：0 + 0 + 0 = 0 、0 + 0 + 0 = 0 和 0 + 0 = 0 。 
s 变为 "0" + "0" + "0" = "000" ，其长度等于 k ，所以返回 "000" 。

提示：

1 <= s.length <= 100
2 <= k <= 100
s 仅由数字（0 - 9）组成。

方法一：模拟 · Go 实现

思考

反复把数字串按长度 $k$ 分组，每组改写成各位之和，直到长度不超过 $k$ 。 $| s | \leq 100$ ，模拟每一轮即可，不必寻找闭式。

当长度仍大于 $k$ 时，步长 $k$ 切片，把切片内数字加总后再转回字符串拼接。数字和至多三位，总长度严格下降，循环很快结束。

根据题意，我们可以模拟题目中的操作过程，直到字符串长度小于等于 $k$ 为止，最后返回字符串即可。

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

func digitSum(s string, k int) string {
	for len(s) > k {
		t := &strings.Builder{}
		n := len(s)
		for i := 0; i < n; i += k {
			x := 0
			for j := i; j < i+k && j < n; j++ {
				x += int(s[j] - '0')
			}
			t.WriteString(strconv.Itoa(x))
		}
		s = t.String()
	}
	return s
}

力扣原题 · Doocs 题解来源

2255. 统计是给定字符串前缀的字符串数目

简单1 种解法

标签：数组、字符串

题目、示例与约束

给你一个字符串数组 words 和一个字符串 s ，其中 words[i] 和 s 只包含 小写英文字母 。

请你返回 words 中是字符串 s 前缀的 字符串数目 。

一个字符串的前缀是出现在字符串开头的子字符串。子字符串 是一个字符串中的连续一段字符序列。

示例 1：

输入：words = ["a","b","c","ab","bc","abc"], s = "abc"
输出：3
解释：
words 中是 s = "abc" 前缀的字符串为：
"a" ，"ab" 和 "abc" 。
所以 words 中是字符串 s 前缀的字符串数目为 3 。

示例 2：

输入：words = ["a","a"], s = "aa"
输出：2
解释：
两个字符串都是 s 的前缀。
注意，相同的字符串可能在 words 中出现多次，它们应该被计数多次。

提示：

1 <= words.length <= 1000
1 <= words[i].length, s.length <= 10
words[i] 和 s 只包含小写英文字母。

方法一：遍历计数 · Go 实现

思考

统计 $w o r d s$ 中有多少个串是 $s$ 的前缀。词数与串长均不超过 $10^{3}$ 与 $10$ ，对每个词判断 $s$ 是否以其开头即可，无需字典树。

直接调用 $startswith$ ，命中则计入。总比较次数与词数乘 $s$ 长度同阶。

我们直接遍历数组 $words$ ，对于每个字符串 $w$ ，判断 $s$ 是否以 $w$ 为前缀，如果是则答案加一。

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

时间复杂度 $O (m \times n)$ ，其中 $m$ 和 $n$ 分别是数组 $words$ 的长度和字符串 $s$ 的长度。空间复杂度 $O (1)$ 。

func countPrefixes(words []string, s string) (ans int) {
	for _, w := range words {
		if strings.HasPrefix(s, w) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2264. 字符串中最大的 3 位相同数字

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 num ，表示一个大整数。如果一个整数满足下述所有条件，则认为该整数是一个 优质整数 ：

该整数是 num 的一个长度为 3 的 子字符串 。
该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数，则返回一个空字符串 "" 。

注意：

子字符串 是字符串中的一个连续字符序列。
num 或优质整数中可能存在 前导零 。

示例 1：

输入：num = "6777133339"
输出："777"
解释：num 中存在两个优质整数："777" 和 "333" 。
"777" 是最大的那个，所以返回 "777" 。

示例 2：

输入：num = "2300019"
输出："000"
解释："000" 是唯一一个优质整数。

示例 3：

输入：num = "42352338"
输出：""
解释：不存在长度为 3 且仅由一个唯一数字组成的整数。因此，不存在优质整数。

提示：

3 <= num.length <= 1000
num 仅由数字（0 - 9）组成

方法一：枚举 · Go 实现

思考

要找 $n u m$ 中出现过的最大「三位相同」子串。长度 $10^{3}$ ，从大到小检查 $999, \dots, 000$ 是否为子串即可，命中即最大。

对 $i$ 从 $9$ 到 $0$ ，判断 $str (i) * 3$ 是否在 $n u m$ 中。都没有则返回空串。

我们可以从大到小枚举每个数字 $i$ ，其中 $0 \leq i \leq 9$ ，然后判断连续的三个 $i$ 构成的字符串 $s$ 是否是 $n u m$ 的子串，若是，直接返回 $s$ 即可。

若枚举完所有的 $i$ 都没有找到满足条件的字符串，则返回空字符串。

时间复杂度 $O (10 \times n)$ ，其中 $n$ 是字符串 $n u m$ 的长度。空间复杂度 $O (1)$ 。

func largestGoodInteger(num string) string {
	for c := '9'; c >= '0'; c-- {
		if s := strings.Repeat(string(c), 3); strings.Contains(num, s) {
			return s
		}
	}
	return ""
}

力扣原题 · Doocs 题解来源

2278. 字母在字符串中的百分比

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 s 和一个字符 letter ，返回在 s 中等于 letter 字符所占的 百分比 ，向下取整到最接近的百分比。

示例 1：

输入：s = "foobar", letter = "o"
输出：33
解释：
等于字母 'o' 的字符在 s 中占到的百分比是 2 / 6 * 100% = 33% ，向下取整，所以返回 33 。

示例 2：

输入：s = "jjjj", letter = "k"
输出：0
解释：
等于字母 'k' 的字符在 s 中占到的百分比是 0% ，所以返回 0 。

提示：

1 <= s.length <= 100
s 由小写英文字母组成
letter 是一个小写英文字母

方法一：计数 · Go 实现

思考

求某字母在串中所占百分比的向下取整。长度不超过 $100$ ，计数后做整数除法即可。

$s . count (letter) \times 100 / / | s |$ 避免浮点。

我们可以遍历字符串 $s$ ，统计其中等于 $letter$ 的字符的个数，然后根据公式 $count \times 100 / len (s)$ 计算百分比。

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

func percentageLetter(s string, letter byte) int {
	return strings.Count(s, string(letter)) * 100 / len(s)
}

力扣原题 · Doocs 题解来源

2288. 价格减免

中等1 种解法

标签：字符串

题目、示例与约束

句子是由若干个单词组成的字符串，单词之间用单个空格分隔，其中每个单词可以包含数字、小写字母、和美元符号 '$' 。如果单词的形式为美元符号后跟着一个非负实数，那么这个单词就表示一个价格。

例如 "$100"、"$23" 和 "$6" 表示价格，而 "100"、"$" 和 "$1e5 不是。

给你一个字符串 sentence 表示一个句子和一个整数 discount 。对于每个表示价格的单词，都在价格的基础上减免 discount% ，并更新该单词到句子中。所有更新后的价格应该表示为一个 恰好保留小数点后两位 的数字。

返回表示修改后句子的字符串。

注意：所有价格最多为 10 位数字。

示例 1：

输入：sentence = "there are $1 $2 and 5$ candies in the shop", discount = 50
输出："there are $0.50 $1.00 and 5$ candies in the shop"
解释：
表示价格的单词是 "$1" 和 "$2" 。 
- "$1" 减免 50% 为 "$0.50" ，所以 "$1" 替换为 "$0.50" 。
- "$2" 减免 50% 为 "$1" ，所以 "$2" 替换为 "$1.00" 。

示例 2：

输入：sentence = "1 2 $3 4 $5 $6 7 8$ $9 $10$", discount = 100
输出："1 2 $0.00 4 $0.00 $0.00 7 8$ $0.00 $10$"
解释：
任何价格减免 100% 都会得到 0 。
表示价格的单词分别是 "$3"、"$5"、"$6" 和 "$9"。
每个单词都替换为 "$0.00"。

提示：

1 <= sentence.length <= 10⁵
sentence 由小写英文字母、数字、' ' 和 '$' 组成
sentence 不含前导和尾随空格
sentence 的所有单词都用单个空格分隔
所有价格都是正整数且不含前导零
所有价格最多为 10 位数字
0 <= discount <= 100

方法一：模拟 · Go 实现

思考

句子中形如 $$$ 加正整数的单词视为价格，打完折后保留两位小数。长度 $10^{5}$ ，按空格拆词后逐个判断即可。

首字符为 $$$ 且其余全是数字则改写为折扣后的金额，再拼回句子。

我们可以将句子按空格分割成单词数组，然后遍历单词数组，对于每个单词，如果其表示价格，则将其更新为减免折扣后的价格。最后将更新后的单词数组拼接成以空格分隔的字符串即可。

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

func discountPrices(sentence string, discount int) string {
	words := strings.Split(sentence, " ")
	for i, w := range words {
		if w[0] == '$' {
			if v, err := strconv.Atoi(w[1:]); err == nil {
				words[i] = fmt.Sprintf("$%.2f", float64(v*(100-discount))/100)
			}
		}
	}
	return strings.Join(words, " ")
}

力扣原题 · Doocs 题解来源

2299. 强密码检验器 II

简单1 种解法

标签：字符串

题目、示例与约束

如果一个密码满足以下所有条件，我们称它是一个强密码：

它有至少 8 个字符。
至少包含 一个小写英文 字母。
至少包含 一个大写英文 字母。
至少包含 一个数字 。
至少包含 一个特殊字符 。特殊字符为："!@#$%^&*()-+" 中的一个。
它不包含 2 个连续相同的字符（比方说 "aab" 不符合该条件，但是 "aba" 符合该条件）。

给你一个字符串 password ，如果它是一个强密码，返回 true，否则返回 false 。

示例 1：

输入：password = "IloveLe3tcode!"
输出：true
解释：密码满足所有的要求，所以我们返回 true 。

示例 2：

输入：password = "Me+You--IsMyDream"
输出：false
解释：密码不包含数字，且包含 2 个连续相同的字符。所以我们返回 false 。

示例 3：

输入：password = "1aB!"
输出：false
解释：密码不符合长度要求。所以我们返回 false 。

提示：

1 <= password.length <= 100
password 包含字母，数字和 "!@#$%^&*()-+" 这些特殊字符。

方法一：模拟 + 位运算 · Go 实现

思考

密码需长度至少 $8$ ，含大小写、数字与特殊字符，且无相邻相同字符。长度不超过 $100$ ，一遍扫描即可同时检查。四类字符是否出现可用四位掩码记录。

长度不足直接失败；遍历时若与前一字符相同也失败；按类型把掩码对应位置 $1$ 。结束时掩码为 $15$ 则四类齐全。

根据题目描述，我们可以模拟检查密码是否满足题目要求的过程。

首先，我们检查密码的长度是否小于 $8$ ，如果是，则返回 $false$ 。

接下来，我们用一个掩码 $mask$ 来记录密码是否包含小写字母、大写字母、数字和特殊字符。我们遍历密码，每次遍历到一个字符，先判断它是否和前一个字符相同，如果是，则返回 $false$ 。然后，根据字符的类型更新掩码 $mask$ 。最后，我们检查掩码 $mask$ 是否为 $15$ ，如果是，则返回 $true$ ，否则返回 $false$ 。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为密码的长度。

func strongPasswordCheckerII(password string) bool {
	if len(password) < 8 {
		return false
	}
	mask := 0
	for i, c := range password {
		if i > 0 && byte(c) == password[i-1] {
			return false
		}
		if unicode.IsLower(c) {
			mask |= 1
		} else if unicode.IsUpper(c) {
			mask |= 2
		} else if unicode.IsDigit(c) {
			mask |= 4
		} else {
			mask |= 8
		}
	}
	return mask == 15
}

力扣原题 · Doocs 题解来源

2315. 统计星号

简单1 种解法

标签：字符串

题目、示例与约束

给你一个字符串 s ，每两个连续竖线 '|' 为一对。换言之，第一个和第二个 '|' 为一对，第三个和第四个 '|' 为一对，以此类推。

请你返回不在竖线对之间，s 中 '*' 的数目。

注意，每个竖线 '|' 都会恰好属于一个对。

示例 1：

输入：s = "l|*e*et|c**o|*de|"
输出：2
解释：不在竖线对之间的字符加粗加斜体后，得到字符串："l|*e*et|c**o|*de|" 。
第一和第二条竖线 '|' 之间的字符不计入答案。
同时，第三条和第四条竖线 '|' 之间的字符也不计入答案。
不在竖线对之间总共有 2 个星号，所以我们返回 2 。

示例 2：

输入：s = "iamprogrammer"
输出：0
解释：在这个例子中，s 中没有星号。所以返回 0 。

示例 3：

输入：s = "yo|uar|e**|b|e***au|tifu|l"
输出：5
解释：需要考虑的字符加粗加斜体后："yo|uar|e**|b|e***au|tifu|l" 。不在竖线对之间总共有 5 个星号。所以我们返回 5 。

提示：

1 <= s.length <= 1000
s 只包含小写英文字母，竖线 '|' 和星号 '*' 。
s 包含偶数个竖线 '|' 。

方法一：模拟 · Go 实现

思考

竖线成对出现，只需统计不在任何一对之间的星号。 $s$ 长度不超过 $1000$ ，一次扫描足够。

用开关 $ok$ 表示当前是否处于成对竖线之外。遇到 | 翻转开关，遇到 * 仅在开关打开时计数。无需真正切分字符串。

我们定义一个整型变量 $ok$ ，表示遇到 * 时是否能计数，初始时 $ok = 1$ ，表示可以计数。

遍历字符串 $s$ ，如果遇到 *，则根据 $ok$ 的值决定是否计数，如果遇到 |，则 $ok$ 的值取反。

最后返回计数的结果。

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

func countAsterisks(s string) (ans int) {
	ok := 1
	for _, c := range s {
		if c == '*' {
			ans += ok
		} else if c == '|' {
			ok ^= 1
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2414. 最长的字母序连续子字符串的长度

中等1 种解法

标签：字符串

题目、示例与约束

字母序连续字符串 是由字母表中连续字母组成的字符串。换句话说，字符串 "abcdefghijklmnopqrstuvwxyz" 的任意子字符串都是 字母序连续字符串 。

例如，"abc" 是一个字母序连续字符串，而 "acb" 和 "za" 不是。

给你一个仅由小写英文字母组成的字符串 s ，返回其最长的字母序连续子字符串的长度。

示例 1：

输入：s = "abacaba"
输出：2
解释：共有 4 个不同的字母序连续子字符串 "a"、"b"、"c" 和 "ab" 。
"ab" 是最长的字母序连续子字符串。

示例 2：

输入：s = "abcde"
输出：5
解释："abcde" 是最长的字母序连续子字符串。

提示：

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

方法一：一次遍历 · Go 实现

思考

连续字母序子串， $n \leq 10^{5}$ ，枚举左右端点多余。相邻字符的 ASCII 差为 $1$ 则当前段延长，否则重置长度为 $1$ ，一遍扫描记录最大值。

我们可以遍历字符串 $s$ ，用一个变量 $ans$ 记录最长的字母序连续子字符串的长度，用另一个变量 $cnt$ 记录当前连续子字符串的长度。初始时 $ans = cnt = 1$ 。

接下来，我们从下标为 $1$ 的字符开始遍历字符串 $s$ ，对于每个字符 $s [i]$ ，如果 $s [i] - s [i - 1] = 1$ ，则说明当前字符和前一个字符是连续的，此时 $cnt = cnt + 1$ ，并更新 $ans = max (ans, cnt)$ ；否则，说明当前字符和前一个字符不连续，此时 $cnt = 1$ 。

最终返回 $ans$ 即可。

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

func longestContinuousSubstring(s string) int {
	ans, cnt := 1, 1
	for i := range s[1:] {
		if s[i+1]-s[i] == 1 {
			cnt++
			ans = max(ans, cnt)
		} else {
			cnt = 1
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

2437. 有效时间的数目

简单2 种解法

标签：字符串、枚举

题目、示例与约束

给你一个长度为 5 的字符串 time ，表示一个电子时钟当前的时间，格式为 "hh:mm" 。最早可能的时间是 "00:00" ，最晚可能的时间是 "23:59" 。

在字符串 time 中，被字符 ? 替换掉的数位是 未知的 ，被替换的数字可能是 0 到 9 中的任何一个。

请你返回一个整数 answer ，将每一个 ? 都用 0 到 9 中一个数字替换后，可以得到的有效时间的数目。

示例 1：

输入：time = "?5:00"
输出：2
解释：我们可以将 ? 替换成 0 或 1 ，得到 "05:00" 或者 "15:00" 。注意我们不能替换成 2 ，因为时间 "25:00" 是无效时间。所以我们有两个选择。

示例 2：

输入：time = "0?:0?"
输出：100
解释：两个 ? 都可以被 0 到 9 之间的任意数字替换，所以我们总共有 100 种选择。

示例 3：

输入：time = "??:??"
输出：1440
解释：小时总共有 24 种选择，分钟总共有 60 种选择。所以总共有 24 * 60 = 1440 种选择。

提示：

time 是一个长度为 5 的有效字符串，格式为 "hh:mm" 。
"00" <= hh <= "23"
"00" <= mm <= "59"
字符串中有的数位是 '?' ，需要用 0 到 9 之间的数字替换。

方法一：枚举 · Go 实现

思考

合法时钟只有 $24 \times 60$ 种，通配符至多四位。枚举全部时刻，按位与模板比较（模板为 ? 则视为匹配）即可。

我们可以直接枚举从 $00 : 00$ 到 $23 : 59$ 的所有时间，然后判断每个时间是否有效，是则答案加一。

枚举结束后将答案返回即可。

时间复杂度 $O (24 \times 60)$ ，空间复杂度 $O (1)$ 。

func countTime(time string) int {
	ans := 0
	for h := 0; h < 24; h++ {
		for m := 0; m < 60; m++ {
			s := fmt.Sprintf("%02d:%02d", h, m)
			ok := 1
			for i := 0; i < 5; i++ {
				if s[i] != time[i] && time[i] != '?' {
					ok = 0
					break
				}
			}
			ans += ok
		}
	}
	return ans
}

方法二：枚举优化 · Go 实现

思考

方法一已穷尽所有时刻。小时与分钟相互独立，分别统计匹配 $00. .23$ 与 $00. .59$ 的个数再相乘，枚举量从 $1440$ 降为 $84$ 。

我们可以分开枚举小时和分钟，统计有多少个小时和分钟满足条件，然后将二者相乘即可。

时间复杂度 $O (24 + 60)$ ，空间复杂度 $O (1)$ 。

func countTime(time string) int {
	f := func(s string, m int) (cnt int) {
		for i := 0; i < m; i++ {
			a := s[0] == '?' || int(s[0]-'0') == i/10
			b := s[1] == '?' || int(s[1]-'0') == i%10
			if a && b {
				cnt++
			}
		}
		return
	}
	return f(time[:2], 24) * f(time[3:], 60)
}

力扣原题 · Doocs 题解来源

2446. 判断两个事件是否存在冲突

简单1 种解法

标签：数组、字符串

题目、示例与约束

给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：

event1 = [startTime₁, endTime₁] 且
event2 = [startTime₂, endTime₂]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现冲突。

如果两个事件之间存在冲突，返回 true ；否则，返回 false 。

示例 1：

输入：event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出：true
解释：两个事件在 2:00 出现交集。

示例 2：

输入：event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]
输出：true
解释：两个事件的交集从 01:20 开始，到 02:00 结束。

示例 3：

输入：event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]
输出：false
解释：两个事件不存在交集。

提示：

event1.length == event2.length == 2
event1[i].length == event2[i].length == 5
startTime₁ <= endTime₁
startTime₂ <= endTime₂
所有事件的时间都按照 HH:MM 格式给出

方法一：字符串比较 · Go 实现

思考

时间格式 $HH:MM$ 可直接按字符串比较。两区间无交当且仅当其一完全在另一之左，即 $e v e n t 1 [0] > e v e n t 2 [1]$ 或 $e v e n t 1 [1] < e v e n t 2 [0]$ 。取反即为冲突。

如果 $e v e n t 1$ 的开始时间大于 $e v e n t 2$ 的结束时间，或者 $e v e n t 1$ 的结束时间小于 $e v e n t 2$ 的开始时间，那么两个事件不会有冲突。否则，两个事件存在冲突。

时间复杂度 $O (1)$ ，空间复杂度 $O (1)$ 。

func haveConflict(event1 []string, event2 []string) bool {
	return !(event1[0] > event2[1] || event1[1] < event2[0])
}

力扣原题 · Doocs 题解来源

2468. 根据限制分割消息

困难1 种解法

标签：字符串、枚举

题目、示例与约束

给你一个字符串 message 和一个正整数 limit 。

你需要根据 limit 将 message 分割成一个或多个部分。每个部分的结尾都是 "<a/b>" ，其中 "b" 用分割出来的总数替换， "a" 用当前部分所在的编号替换，编号从 1 到 b 依次编号。除此以外，除了最后一部分长度 小于等于 limit 以外，其他每一部分（包括结尾部分）的长度都应该等于 limit 。

你需要确保分割后的结果数组，删掉每部分的结尾并 按顺序 连起来后，能够得到 message 。同时，结果数组越短越好。

请你返回 message 分割后得到的结果数组。如果无法按要求分割 message ，返回一个空数组。

示例 1：

输入：message = "this is really a very awesome message", limit = 9
输出：["thi<1/14>","s i<2/14>","s r<3/14>","eal<4/14>","ly <5/14>","a v<6/14>","ery<7/14>"," aw<8/14>","eso<9/14>","me<10/14>"," m<11/14>","es<12/14>","sa<13/14>","ge<14/14>"]
解释：
前面 9 个部分分别从 message 中得到 3 个字符。
接下来的 5 个部分分别从 message 中得到 2 个字符。
这个例子中，包含最后一个部分在内，每个部分的长度都为 9 。
可以证明没有办法分割成少于 14 个部分。

示例 2：

输入：message = "short message", limit = 15
输出：["short mess<1/2>","age<2/2>"]
解释：
在给定限制下，字符串可以分成两个部分：
- 第一个部分包含 10 个字符，长度为 15 。
- 第二个部分包含 3 个字符，长度为 8 。

提示：

1 <= message.length <= 10⁴
message 只包含小写英文字母和 ' ' 。
1 <= limit <= 10⁴

方法一：枚举分段数量 + 模拟 · Go 实现

思考

每段带后缀 $< j / k >$ ，总长度上限 $l i m i t$ 。 $n \leq 10^{4}$ ，从 $k = 1$ 枚举段数：所有下标数字、总段数字与三个符号的长度可 $O (1)$ 累加。剩余容量 $\geq n$ 时按 $l i m i t$ 切正文并接上后缀。

我们设字符串 message 的长度为 $n$ ，分段数量为 $k$ 。

根据题意，如果 $k > n$ ，表示我们可以将字符串划分成超过 $n$ 段，由于字符串长度仅为 $n$ ，若划分成超过 $n$ 段必然导致有部分段的长度为 $0$ ，可以删去。因此，我们只需要将 $k$ 的取值范围限制在 $[1, . . n]$ 即可。

从小到大枚举分段数量 $k$ ，记所有分段中 $a$ 段的长度为 $s a$ ，所有分段中 $b$ 段的长度为 $s b$ ，所有分段中符号（包括尖括号和斜杠）的长度为 $s c$ 。

那么 $s a$ 的值为 $\sum_{j = 1}^{k} l e n (s_{j})$ ，可以直接通过前缀和求出；而 $s b$ 的值为 $l e n (s t r (k)) \times k$ ；另外 $s c$ 的值为 $3 \times k$ 。

因此，所有分段剩余可填充的字符数为 $l i m i t \times k - (s a + s b + s c)$ ，如果该值大于等于 $n$ 则说明可以将字符串划分成 $k$ 段，直接构造答案返回即可。

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

func splitMessage(message string, limit int) (ans []string) {
	n := len(message)
	sa := 0
	for k := 1; k <= n; k++ {
		lk := len(strconv.Itoa(k))
		sa += lk
		sb := lk * k
		sc := 3 * k
		if limit*k-(sa+sb+sc) >= n {
			i := 0
			for j := 1; j <= k; j++ {
				tail := "<" + strconv.Itoa(j) + "/" + strconv.Itoa(k) + ">"
				t := message[i:min(i+limit-len(tail), n)] + tail
				ans = append(ans, t)
				i += limit - len(tail)
			}
			break
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2490. 回环句

简单2 种解法

标签：字符串

题目、示例与约束

句子是由单个空格分隔的一组单词，且不含前导或尾随空格。

例如，"Hello World"、"HELLO"、"hello world hello world" 都是符合要求的句子。

单词仅由大写和小写英文字母组成。且大写和小写字母会视作不同字符。

如果句子满足下述全部条件，则认为它是一个 回环句 ：

句子中每个单词的最后一个字符等于下一个单词的第一个字符。
最后一个单词的最后一个字符和第一个单词的第一个字符相等。

例如，"leetcode exercises sound delightful"、"eetcode"、"leetcode eats soul" 都是回环句。然而，"Leetcode is cool"、"happy Leetcode"、"Leetcode" 和 "I like Leetcode" 都不是回环句。

给你一个字符串 sentence ，请你判断它是不是一个回环句。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：sentence = "leetcode exercises sound delightful"
输出：true
解释：句子中的单词是 ["leetcode", "exercises", "sound", "delightful"] 。
- leetcode 的最后一个字符和 exercises 的第一个字符相等。
- exercises 的最后一个字符和 sound 的第一个字符相等。
- sound 的最后一个字符和 delightful 的第一个字符相等。
- delightful 的最后一个字符和 leetcode 的第一个字符相等。
这个句子是回环句。

示例 2：

输入：sentence = "eetcode"
输出：true
解释：句子中的单词是 ["eetcode"] 。
- eetcode 的最后一个字符和 eetcode 的第一个字符相等。
这个句子是回环句。

示例 3：

输入：sentence = "Leetcode is cool"
输出：false
解释：句子中的单词是 ["Leetcode", "is", "cool"] 。
- Leetcode 的最后一个字符和 is 的第一个字符 不 相等。 
这个句子 不 是回环句。

提示：

1 <= sentence.length <= 500
sentence 仅由大小写英文字母和空格组成
sentence 中的单词由单个空格进行分隔
不含任何前导或尾随空格

方法一：模拟 · Go 实现

思考

环形句要求相邻词首尾字母相同，且首词开头等于末词结尾。按空格切开后检查 $s [- 1]$ 与下一词 $[0]$ （末词接到首词）。

我们将字符串按照空格分割成单词，然后判断每个单词的最后一个字符和下一个单词的第一个字符是否相等，如果不相等则返回 false，否则遍历完所有单词后返回 true。

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

func isCircularSentence(sentence string) bool {
	ss := strings.Split(sentence, " ")
	n := len(ss)
	for i, s := range ss {
		if s[len(s)-1] != ss[(i+1)%n][0] {
			return false
		}
	}
	return true
}

方法二：模拟（空间优化） · Go 实现

思考

方法一产生了单词数组。原串无首尾空格，首尾字符相等即首末词衔接；中间每个空格两侧字符相等即相邻词衔接。额外空间降至 $O (1)$ 。

我们可以先判断字符串的第一个字符和最后一个字符是否相等，如果不相等则返回 false，否则遍历字符串，如果当前字符是空格，则判断前一个字符和后一个字符是否相等，如果不相等则返回 false，否则遍历完所有字符后返回 true。

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

func isCircularSentence(s string) bool {
	n := len(s)
	if s[0] != s[n-1] {
		return false
	}
	for i := 1; i < n; i++ {
		if s[i] == ' ' && s[i-1] != s[i+1] {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

2496. 数组中字符串的最大值

简单1 种解法

标签：数组、字符串

题目、示例与约束

一个由字母和数字组成的字符串的值定义如下：

如果字符串只包含数字，那么值为该字符串在 10 进制下的所表示的数字。
否则，值为字符串的长度。

给你一个字符串数组 strs ，每个字符串都只由字母和数字组成，请你返回 strs 中字符串的 最大值 。

示例 1：

输入：strs = ["alic3","bob","3","4","00000"]
输出：5
解释：
- "alic3" 包含字母和数字，所以值为长度 5 。
- "bob" 只包含字母，所以值为长度 3 。
- "3" 只包含数字，所以值为 3 。
- "4" 只包含数字，所以值为 4 。
- "00000" 只包含数字，所以值为 0 。
所以最大的值为 5 ，是字符串 "alic3" 的值。

示例 2：

输入：strs = ["1","01","001","0001"]
输出：1
解释：
数组中所有字符串的值都是 1 ，所以我们返回 1 。

提示：

1 <= strs.length <= 100
1 <= strs[i].length <= 9
strs[i] 只包含小写英文字母和数字。

方法一：模拟 · Go 实现

思考

字符串要么是十进制数值，要么含字母则取其长度。长度至多 $9$ ，对每个串判断是否全为数字后取 $int$ 或 $len$ ，再求最大。

我们定义一个函数 $f (s)$ ，用于计算字符串 $s$ 的值。如果 $s$ 只包含数字，那么 $f (s)$ 就是 $s$ 在十进制下的值；否则 $f (s)$ 就是 $s$ 的长度。

答案为 $max_{s \in strs} f (s)$ 。

时间复杂度 $O (n)$ ，其中 $n$ 是数组 $s t r s$ 的长度。空间复杂度 $O (1)$ 。

func maximumValue(strs []string) (ans int) {
	f := func(s string) (x int) {
		for _, c := range s {
			if c >= 'a' && c <= 'z' {
				return len(s)
			}
			x = x*10 + int(c-'0')
		}
		return
	}
	for _, s := range strs {
		if x := f(s); ans < x {
			ans = x
		}
	}
	return
}

力扣原题 · Doocs 题解来源

2515. 到目标字符串的最短距离

简单1 种解法

标签：数组、字符串

题目、示例与约束

给你一个下标从 0 开始的环形字符串数组 words 和一个字符串 target 。环形数组 意味着数组首尾相连。

形式上， words[i] 的下一个元素是 words[(i + 1) % n] ，而 words[i] 的前一个元素是 words[(i - 1 + n) % n] ，其中 n 是 words 的长度。

从 startIndex 开始，你一次可以用 1 步移动到下一个或者前一个单词。

返回到达目标字符串 target 所需的最短距离。如果 words 中不存在字符串 target ，返回 -1 。

示例 1：

输入：words = ["hello","i","am","leetcode","hello"], target = "hello", startIndex = 1
输出：1
解释：从下标 1 开始，可以经由以下步骤到达 "hello" ：
- 向右移动 3 个单位，到达下标 4 。
- 向左移动 2 个单位，到达下标 4 。
- 向右移动 4 个单位，到达下标 0 。
- 向左移动 1 个单位，到达下标 0 。
到达 "hello" 的最短距离是 1 。

示例 2：

输入：words = ["a","b","leetcode"], target = "leetcode", startIndex = 0
输出：1
解释：从下标 0 开始，可以经由以下步骤到达 "leetcode" ：
- 向右移动 2 个单位，到达下标 2 。
- 向左移动 1 个单位，到达下标 2 。
到达 "leetcode" 的最短距离是 1 。

示例 3：

输入：words = ["i","eat","leetcode"], target = "ate", startIndex = 0
输出：-1
解释：因为 words 中不存在字符串 "ate" ，所以返回 -1 。

提示：

1 <= words.length <= 100
1 <= words[i].length <= 100
words[i] 和 target 仅由小写英文字母组成
0 <= startIndex < words.length

方法一：一次遍历 · Go 实现

思考

数组首尾相接，求从 $startIndex$ 走到某个等于 $target$ 的下标的最少步数。双向逐步扩散在 $n \leq 100$ 时可行，但每个 $target$ 出现位置与起点的环上距离都可闭式求出。

遍历所有等于 $target$ 的下标 $i$ ，环距为 $min (| i - startIndex |, n - | i - startIndex |)$ ，取最小者；若从未出现则返回 $- 1$ 。

我们遍历数组 $words$ ，找到与 $target$ 相等的单词，计算其与 $startIndex$ 的距离 $t$ ，则此时的最短距离为 $min (t, n - t)$ ，我们只需要不断更新最小值即可。

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

func closestTarget(words []string, target string, startIndex int) int {
	n := len(words)
	ans := n
	for i, w := range words {
		if w == target {
			t := i - startIndex
			if t < 0 {
				t = -t
			}
			ans = min(ans, t, n-t)
		}
	}
	if ans == n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

2586. 统计范围内的元音字符串数

简单1 种解法

标签：数组、字符串、计数

题目、示例与约束

给你一个下标从 0 开始的字符串数组 words 和两个整数：left 和 right 。

如果字符串以元音字母开头并以元音字母结尾，那么该字符串就是一个 元音字符串 ，其中元音字母是 'a'、'e'、'i'、'o'、'u' 。

返回 words[i] 是元音字符串的数目，其中 i 在闭区间 [left, right] 内。

示例 1：

输入：words = ["are","amy","u"], left = 0, right = 2
输出：2
解释：
- "are" 是一个元音字符串，因为它以 'a' 开头并以 'e' 结尾。
- "amy" 不是元音字符串，因为它没有以元音字母结尾。
- "u" 是一个元音字符串，因为它以 'u' 开头并以 'u' 结尾。
在上述范围中的元音字符串数目为 2 。

示例 2：

输入：words = ["hey","aeo","mu","ooo","artro"], left = 1, right = 4
输出：3
解释：
- "aeo" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
- "mu" 不是元音字符串，因为它没有以元音字母开头。
- "ooo" 是一个元音字符串，因为它以 'o' 开头并以 'o' 结尾。
- "artro" 是一个元音字符串，因为它以 'a' 开头并以 'o' 结尾。
在上述范围中的元音字符串数目为 3 。

提示：

1 <= words.length <= 1000
1 <= words[i].length <= 10
words[i] 仅由小写英文字母组成
0 <= left <= right < words.length

方法一：模拟 · Go 实现

思考

统计下标落在 $[left, right]$ 且首尾都是元音的单词。区间长度与 $n$ 同阶，直接切片判断即可，无需前缀和。

我们只需要遍历区间 $[l e f t, . . r i g h t]$ 内的字符串，判断其是否以元音字母开头和结尾即可。若是，则答案加一。

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

时间复杂度 $O (m)$ ，空间复杂度 $O (1)$ 。其中 $m = r i g h t - l e f t + 1$ 。

func vowelStrings(words []string, left int, right int) (ans int) {
	check := func(c byte) bool {
		return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'
	}
	for _, w := range words[left : right+1] {
		if check(w[0]) && check(w[len(w)-1]) {
			ans++
		}
	}
	return
}

力扣原题 · Doocs 题解来源

LeetCode Go · 字符串（3） ​

1945. 字符串转化后的各位数字之和 ​

1957. 删除字符使字符串变好 ​

1967. 作为子字符串出现在单词中的字符串数目 ​

2011. 执行操作后的变量值 ​

2042. 检查句子中的数字是否递增 ​

2047. 句子中的有效单词数 ​

2075. 解码斜向换位密码 ​

2114. 句子中的最多单词数 ​

2120. 执行所有后缀指令 ​

2124. 检查是否所有 A 都在 B 之前 ​

2129. 将标题首字母大写 ​

2138. 将字符串拆分为若干长度为 k 的组 ​

2185. 统计包含给定前缀的字符串 ​

2194. Excel 表中某个范围内的单元格 ​

2232. 向表达式添加括号后的最小结果 ​

2243. 计算字符串的数字和 ​

2255. 统计是给定字符串前缀的字符串数目 ​

2264. 字符串中最大的 3 位相同数字 ​

2278. 字母在字符串中的百分比 ​

2288. 价格减免 ​

2299. 强密码检验器 II ​

2315. 统计星号 ​

2414. 最长的字母序连续子字符串的长度 ​

2437. 有效时间的数目 ​

2446. 判断两个事件是否存在冲突 ​

2468. 根据限制分割消息 ​

2490. 回环句 ​

2496. 数组中字符串的最大值 ​

2515. 到目标字符串的最短距离 ​

2586. 统计范围内的元音字符串数 ​

继续阅读

LeetCode Go · 字符串（3）

1945. 字符串转化后的各位数字之和

1957. 删除字符使字符串变好

1967. 作为子字符串出现在单词中的字符串数目

2011. 执行操作后的变量值

2042. 检查句子中的数字是否递增

2047. 句子中的有效单词数

2075. 解码斜向换位密码

2114. 句子中的最多单词数

2120. 执行所有后缀指令

2124. 检查是否所有 A 都在 B 之前

2129. 将标题首字母大写

2138. 将字符串拆分为若干长度为 k 的组

2185. 统计包含给定前缀的字符串

2194. Excel 表中某个范围内的单元格

2232. 向表达式添加括号后的最小结果

2243. 计算字符串的数字和

2255. 统计是给定字符串前缀的字符串数目

2264. 字符串中最大的 3 位相同数字

2278. 字母在字符串中的百分比

2288. 价格减免

2299. 强密码检验器 II

2315. 统计星号

2414. 最长的字母序连续子字符串的长度

2437. 有效时间的数目

2446. 判断两个事件是否存在冲突

2468. 根据限制分割消息

2490. 回环句

2496. 数组中字符串的最大值

2515. 到目标字符串的最短距离

2586. 统计范围内的元音字符串数