LeetCode刷题------字符串

目录

LeetCode：344.反转字符串

LeetCode：541. 反转字符串II

LeetCode：剑指Offer 05.替换空格

LeetCode：151.翻转字符串里的单词

LeetCode：剑指Offer58-II.左旋转字符串

LeetCode：28. 实现 strStr()

LeetCode：459.重复的子字符串

---

定义两个指针（也可以说是索引下标），一个从字符串前面，一个从字符串后面，两个指针同时向中间移动，并交换元素。

var reverseString = function(s) {let l = -1, r = s.length;while(++l < --r) {[s[l], s[r]] = [s[r], s[l]];}};

LeetCode：541. 反转字符串II

var reverseStr = function(s, k) {let resArr = s.split("");for (let i=0; i<s.length; i+=2*k) {let l = i-1, r = i + k > s.length ? s.length : i + k;while(++l < --r) {[resArr[l], resArr[r]] = [resArr[r], resArr[l]];}}return resArr.join("");};

LeetCode：剑指Offer 05.替换空格

从前向后填充就是O(n^2)的算法了，因为每次添加元素都要将添加元素之后的所有元素向后移动。其实很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。这么做有两个好处：

1. 不用申请新数组。
2. 从后向前填充元素，避免了从前向后填充元素时，每次添加元素都要将添加元素之后的所有元素向后移动的问题。

 var replaceSpace = function(s) {// 字符串转为数组const strArr = Array.from(s);let count = 0;// 计算空格数量for(let i = 0; i < strArr.length; i++) {if (strArr[i] === ' ') {count++;}}let left = strArr.length - 1;let right = strArr.length + count * 2 - 1;while(left >= 0) {if (strArr[left] === ' ') {strArr[right--] = '0';strArr[right--] = '2';strArr[right--] = '%';left--;} else {strArr[right--] = strArr[left--];}}// 数组转字符串return strArr.join('');
};

LeetCode：151.翻转字符串里的单词

提高一下本题的难度：不要使用辅助空间，空间复杂度要求为O(1)。不能使用辅助空间之后，那么只能在原字符串上下功夫了。想一下，我们将整个字符串都反转过来，那么单词的顺序指定是倒序了，只不过单词本身也倒序了，那么再把单词反转一下，单词不就正过来了。所以解题思路如下：

• 移除多余空格
• 将整个字符串反转
• 将每个单词反转

举个例子，源字符串为："the sky is blue "

• 移除多余空格 : "the sky is blue"
• 字符串反转："eulb si yks eht"
• 单词反转："blue is sky the"

 var reverseWords = function(s) {// 字符串转数组const strArr = Array.from(s);// 移除多余空格removeExtraSpaces(strArr);// 翻转reverse(strArr, 0, strArr.length - 1);let start = 0;for(let i = 0; i <= strArr.length; i++) {if (strArr[i] === ' ' || i === strArr.length) {// 翻转单词reverse(strArr, start, i - 1);start = i + 1;}}return strArr.join('');
};// 删除多余空格
function removeExtraSpaces(strArr) {let slowIndex = 0;let fastIndex = 0;while(fastIndex < strArr.length) {// 移除开始位置和重复的空格if (strArr[fastIndex] === ' ' && (fastIndex === 0 || strArr[fastIndex - 1] === ' ')) {fastIndex++;} else {strArr[slowIndex++] = strArr[fastIndex++];}}// 移除末尾空格strArr.length = strArr[slowIndex - 1] === ' ' ? slowIndex - 1 : slowIndex;
}// 翻转从 start 到 end 的字符
function reverse(strArr, start, end) {let left = start;let right = end;while(left < right) {// 交换[strArr[left], strArr[right]] = [strArr[right], strArr[left]];left++;right--;}
}

LeetCode：剑指Offer58-II.左旋转字符串

// 版本一var reverseLeftWords = function(s, n) {const length = s.length;let i = 0;while (i < length - n) {s = s[length - 1] + s;i++;}return s.slice(0, length);
};// 版本二：在原字符串上修改var reverseLeftWords = function (s, n) {/** Utils */function reverseWords(strArr, start, end) {let temp;while (start < end) {temp = strArr[start];strArr[start] = strArr[end];strArr[end] = temp;start++;end--;}}/** Main code */let strArr = s.split('');let length = strArr.length;reverseWords(strArr, 0, length - 1);reverseWords(strArr, 0, length - n - 1);reverseWords(strArr, length - n, length - 1);return strArr.join('');
};

LeetCode：28. 实现 strStr()

本题是KMP 经典题目。KMP主要应用在字符串匹配上。KMP的经典思想就是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。所以如何记录已经匹配的文本内容，是KMP的重点，也是next数组肩负的重任。

next数组就是一个前缀表。前缀表是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

前缀表是如何记录的呢？首先要知道前缀表的任务是当前位置匹配失败，找到之前已经匹配上的位置，再重新匹配，此也意味着在某个字符失配时，前缀表会告诉你下一步匹配中，模式串应该跳到哪个位置。

构造next数组其实就是计算模式串s，前缀表的过程。 主要有如下三步：

1. 初始化
2. 处理前后缀不相同的情况
3. 处理前后缀相同的情况

// 前缀表统一减一var strStr = function (haystack, needle) {if (needle.length === 0)return 0;const getNext = (needle) => {let next = [];let j = -1;next.push(j);for (let i = 1; i < needle.length; ++i) {while (j >= 0 && needle[i] !== needle[j + 1])j = next[j];if (needle[i] === needle[j + 1])j++;next.push(j);}return next;}let next = getNext(needle);let j = -1;for (let i = 0; i < haystack.length; ++i) {while (j >= 0 && haystack[i] !== needle[j + 1])j = next[j];if (haystack[i] === needle[j + 1])j++;if (j === needle.length - 1)return (i - needle.length + 1);}return -1;
};// 前缀表统一不减一var strStr = function (haystack, needle) {if (needle.length === 0)return 0;const getNext = (needle) => {let next = [];let j = 0;next.push(j);for (let i = 1; i < needle.length; ++i) {while (j > 0 && needle[i] !== needle[j])j = next[j - 1];if (needle[i] === needle[j])j++;next.push(j);}return next;}let next = getNext(needle);let j = 0;for (let i = 0; i < haystack.length; ++i) {while (j > 0 && haystack[i] !== needle[j])j = next[j - 1];if (haystack[i] === needle[j])j++;if (j === needle.length)return (i - needle.length + 1);}return -1;
};

LeetCode：459.重复的子字符串

//前缀表统一减一var repeatedSubstringPattern = function (s) {if (s.length === 0)return false;const getNext = (s) => {let next = [];let j = -1;next.push(j);for (let i = 1; i < s.length; ++i) {while (j >= 0 && s[i] !== s[j + 1])j = next[j];if (s[i] === s[j + 1])j++;next.push(j);}return next;}let next = getNext(s);if (next[next.length - 1] !== -1 && s.length % (s.length - (next[next.length - 1] + 1)) === 0)return true;return false;
};//前缀表统一不减一var repeatedSubstringPattern = function (s) {if (s.length === 0)return false;const getNext = (s) => {let next = [];let j = 0;next.push(j);for (let i = 1; i < s.length; ++i) {while (j > 0 && s[i] !== s[j])j = next[j - 1];if (s[i] === s[j])j++;next.push(j);}return next;}let next = getNext(s);if (next[next.length - 1] !== 0 && s.length % (s.length - next[next.length - 1]) === 0)return true;return false;
};