leetcode - 字符串

字符串

466. 统计重复个数

题目

定义 str = [s, n] 表示 str 由 n 个字符串 s 连接构成。

• 例如，str == ["abc", 3] =="abcabcabc" 。

如果可以从 s2( )中删除某些字符使其变为 s1，则称字符串 s1( )可以从字符串 s2 获得。

• 例如，根据定义，s1 = "abc" 可以从 s2 = "abdbec" 获得，仅需要删除加粗且用斜体标识的字符。

现在给你两个字符串 s1 和 s2 和两个整数 n1 和 n2 。由此构造得到两个字符串，其中 str1 = [s1, n1]、str2 = [s2, n2] 。
请你找出一个最大整数 m ，以满足 str = [str2, m] 可以从 str1 获得。

示例 1：
输入： s1 = “acb”, n1 = 4, s2 = “ab”, n2 = 2 输出： 2
示例 2：
输入： s1 = “acb”, n1 = 1, s2 = “acb”, n2 = 1 输出： 1

提示：

• 1 <= s1.length, s2.length <= 100

• s1 和 s2 由小写英文字母组成

• 1 <= n1, n2 <= 10(6)

题解

/*** @param {string} s1* @param {number} n1* @param {string} s2* @param {number} n2* @return {number}*/
var getMaxRepetitions = function (s1, n1, s2, n2) {let indexMap = new Map();let countS1 = 0,countS2 = 0;let s2p = 0;while (countS1 < n1) {let prev = indexMap.get(s2p);if (!prev) {indexMap.set(s2p, [countS1, countS2]);} else {// 循环节 下一个s1 对应的 s2p 索引有相同时// 循环节循环的次数 向下取整let t = ((n1 - prev[0]) / (countS1 - prev[0])) | 0;countS2 = prev[1] + t * (countS2 - prev[1]);countS1 = prev[0] + t * (countS1 - prev[0]);// 清楚之前的循环记录indexMap.clear();// 整除if (countS1 === n1) break;}// 循环s1for (let i = 0; i < s1.length; i++) {if (s1[i] === s2[s2p]) {s2p++;if (s2p === s2.length) {s2p = 0;countS2++;}}}countS1++;}return (countS2 / n2) | 0;
};

514. 自由之路

题目

电子游戏“辐射4”中，任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘，并使用表盘拼写特定关键词才能开门。
给定一个字符串 ring ，表示刻在外环上的编码；给定另一个字符串 key ，表示需要拼写的关键词。您需要算出能够拼写关键词中所有字符的最少步数。
最初，ring 的第一个字符与 12:00 方向对齐。您需要顺时针或逆时针旋转 ring 以使 key 的一个字符在 12:00 方向对齐，然后按下中心按钮，以此逐个拼写完 key 中的所有字符。
旋转 ring 拼出 key 字符 key[i] 的阶段中：

1. 您可以将 ring 顺时针或逆时针旋转 一个位置 ，计为1步。旋转的最终目的是将字符串 ring 的一个字符与 12:00 方向对齐，并且这个字符必须等于字符 key[i] 。

2. 如果字符 key[i] 已经对齐到12:00方向，您需要按下中心按钮进行拼写，这也将算作 1 步。按完之后，您可以开始拼写 key 的下一个字符（下一阶段）, 直至完成所有拼写。

示例 1：

输入: ring = “godding”, key = “gd” 输出: 4 解释: 对于 key 的第一个字符 ‘g’，已经在正确的位置, 我们只需要1步来拼写这个字符。 对于 key 的第二个字符 ‘d’，我们需要逆时针旋转 ring “godding” 2步使它变成 “ddinggo”。 当然, 我们还需要1步进行拼写。 因此最终的输出是 4。
示例 2:
输入: ring = “godding”, key = “godding” 输出: 13

提示：

• 1 <= ring.length, key.length <= 100

• ring 和 key 只包含小写英文字母

• 保证 字符串 key 一定可以由字符串 ring 旋转拼出

题解

/*** @param {string} ring* @param {string} key* @return {number}*/
var findRotateSteps = function (ring, key) {// 外环编码相同字母索引放到同一数组const ringMap = {};for (let i = 0; i < ring.length; i++) {const word = ring[i];if (ringMap[word]) {ringMap[word].push(i);} else {ringMap[word] = [i];}}// 重复计算会超时 由于 1 <= ring.length, key.length <= 100 所以可以搞个备忘录const memo = new Array(ring.length); //  相同编码索引开始，终点索引相同 直接取对应的最小步长function bfs(ringIndex, keyIndex) {if (keyIndex == key.length) return 0;const stepMemo = memo[ringIndex]?.[keyIndex];if (stepMemo) return stepMemo;// 字母对应外编码多个位置的数组const arr = ringMap[key[keyIndex]];let minStep = Infinity;// 找到这个字母不同位置、不同方向旋转最小的步长for (let item of arr) {// 同一个字母 不同方向移动步长const l =ringIndex - item >= 0? ringIndex - item: ringIndex - item + ring.length;const r = ring.length - l;// 不同旋转方向最小步长const min = Math.min(l, r);minStep = Math.min(minStep, min + bfs(item, keyIndex + 1));}memo[ringIndex] = { ...memo[ringIndex], [keyIndex]: minStep };return minStep;}// 按下按钮需要一步，key个字母就是key.lengthreturn key.length + bfs(0, 0);
};

3305. 元音辅音字符串计数 I

题目

给你一个字符串 word 和一个 非负 整数 k。
返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：
输入： word = “aeioqq”, k = 1
输出： 0
解释：
不存在包含所有元音字母的子字符串。
示例 2：
输入： word = “aeiou”, k = 0
输出： 1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。
示例 3：
输入： word = “ieaouqqieaouqq”, k = 1
输出： 3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：

• word[0..5]，即 "ieaouq"。

• word[6..11]，即 "qieaou"。

• word[7..12]，即 "ieaouq"。

提示：

• 5 <= word.length <= 250

• word 仅由小写英文字母组成。

• 0 <= k <= word.length - 5

题解

var countOfSubstrings = function (word, k) {let sum = 0;let start = 0;let end = start + 5 + k;while (start < word.length - 4 - k) {const itemStr = word.substring(start, end);const vowelWordMap = {a: 0,e: 0,i: 0,o: 0,u: 0,};for (let j = 0; j < itemStr.length; j++) {if (!isNaN(vowelWordMap[itemStr[j]])) vowelWordMap[itemStr[j]] += 1;}let vowelWordSum = 0;let isTrueStr = true;for (let key in vowelWordMap) {vowelWordSum += vowelWordMap[key];if (vowelWordMap[key] < 1) {isTrueStr = false;break;}}if (isTrueStr && end - start - vowelWordSum === k) {sum++;}end++;if (end > word.length) {start++;end = start + 5 + k;}}return sum;
};

LCR 018. 验证回文串

题目

给定一个字符串 s ，验证 s 是否是 回文串 ，只考虑字母和数字字符，可以忽略字母的大小写。
本题中，将空字符串定义为有效的 回文串 。

示例 1：
输入: s = “A man, a plan, a canal: Panama” 输出: true 解释： “amanaplanacanalpanama” 是回文串
示例 2：
输入: s = “race a car” 输出: false 解释： “raceacar” 不是回文串

提示：

• 1 <= s.length <= 2 * 10(5)

• 字符串 s 由 ASCII 字符组成

题解

/*** @param {string} s* @return {boolean}*/
var isPalindrome = function (s) {if (!s) {return false;}let startIndex = 0;let endIndex = s.length - 1;while (startIndex < endIndex) {const startItem = s[startIndex].toLocaleLowerCase();const endItem = s[endIndex].toLocaleLowerCase();const isStartMatching = /\d|[a-z]/g.test(startItem);if (!isStartMatching) {startIndex++;continue;}const isEndMatching = /\d|[a-z]/g.test(endItem);if (!isEndMatching) {endIndex--;continue;}if (startItem === endItem) {startIndex++;endIndex--;continue;} else {return false;}}return true;
};