字符串

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);
};

647. 回文子串

題目

給你一個字符串 s ，請你統計并返回這個字符串中 回文子串 的數目。
回文字符串 是正著讀和倒過來讀一樣的字符串。
子字符串 是字符串中的由連續字符組成的一個序列。

示例 1：
輸入： s = “abc” 輸出： 3 解釋： 三個回文子串: “a”, “b”, “c”
示例 2：
輸入： s = “aaa” 輸出： 6 解釋： 6個回文子串: “a”, “a”, “a”, “aa”, “aa”, “aaa”

提示：

• 1 <= s.length <= 1000

• s 由小寫英文字母組成

題解

/*** @param {string} s* @return {number}*/
var countSubstrings = function(s) {const n=s.length;let myNumber=0;for(var i=0;i<2*n-1;i++){//2n-1個回文中心let l=i/2;let r=i/2+(i%2);while(l>=0&&r<n&&s.charAt(l)===s.charAt(r)){//charAt(1.5)===charAt(1)l--r++myNumber++}}return myNumber};

709. 轉換成小寫字母

題目

給你一個字符串 s ，將該字符串中的大寫字母轉換成相同的小寫字母，返回新的字符串。

示例 1：
輸入： s = “Hello” 輸出： “hello”
示例 2：
輸入： s = “here” 輸出： “here”
示例 3：
輸入： s = “LOVELY” 輸出： “lovely”

提示：

• 1 <= s.length <= 100

• s 由 ASCII 字符集中的可打印字符組成

題解

/*** @param {string} str* @return {string}*/
var toLowerCase = function (str) {let startA = 65;//大寫字母A到Z，對應的 ASCII 碼值范圍是65到90。let endZ = 90;// let starta=97;//小寫字母a到z，對應的 ASCII 碼值范圍是97到122。// let endz=122;let res = "";for (var i = 0; i < str.length; i++) {let charcode = str.charCodeAt(i);if (charcode >= startA && charcode <= endZ) {res += String.fromCharCode(charcode + 32);} else {res += str.charAt(i);}}return res;
};

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;
};