代码随想录算法训练营第九天 | 151-翻转字符串里的单词、Carl55-右旋转字符串、28-实现strStr()、459-重复的子字符串
LeetCode151 翻转字符串里的单词
题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/description/
文章讲解：https://programmercarl.com/0151.翻转字符串里的单词.html
视频讲解：https://www.bilibili.com/video/BV1uT41177fX/?vd_source=b989f2b109eb3b17e8178154a7de7a51
首先先去除字符串首尾和行中的多余空格，再将整个字符串反转，最后将每个单词单独再反转就可以达到题目要求
使用快慢指针的写法，快指针优先出发，遍历反转的字符串找空格位置，找到空格位置即[slow，fast-1]区间为一个单词，单独进行反转
快指针到达str.length()以后，[slow，fast-1]即为最后一个单词，反转后结束循环
class Solution {public String reverseWords(String s) {// 去除字符串s首尾及行中多余空格StringBuilder str = deleteMulSpace(s);// 将字符串整体翻转reverseString(str, 0, str.length()-1);// 将各个单词单独翻转reverseEachWord(str);return str.toString();}public StringBuilder deleteMulSpace(String s){int left = 0;int right = s.length() - 1;while(s.charAt(left) == ' '){left++;}while(s.charAt(right) == ' '){right--;}StringBuilder sb = new StringBuilder();while(left <= right){char ch = s.charAt(left);if(ch != ' ' || sb.charAt(sb.length() - 1) != ' '){sb.append(ch);}left++;}return sb;}public void reverseString(StringBuilder sb, int start, int end){while(start < end){char temp = sb.charAt(start);sb.setCharAt(start, sb.charAt(end));sb.setCharAt(end, temp);start++;end--;}}public void reverseEachWord(StringBuilder sb){int slow = 0;int fast = 1;while(fast < sb.length()){while(fast < sb.length() && sb.charAt(fast) != ' '){fast++;}reverseString(sb, slow, fast-1);slow = fast + 1;fast = slow + 1;}}
}
Carl55 右旋转字符串
题目链接：https://kamacoder.com/problempage.php?pid=1065
文章讲解：https://programmercarl.com/kamacoder/0055.右旋字符串.html
第一次解，想到的是用StringBuilder先存字符串后k个字符，再把剩下的字符存进去，即可完成题目要求
看了题解后，又做了一遍。先将后k个字符进行反转，再将前面的字符进行反转，最后再将整个字符串进行反转，也能达成题目要求，神奇
LeetCode28 实现strStr()
题目链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
文章讲解：https://programmercarl.com/0028.实现strStr.html
视频讲解：
https://www.bilibili.com/video/BV1PD4y1o7nd/?vd_source=b989f2b109eb3b17e8178154a7de7a51
https://www.bilibili.com/video/BV1M5411j7Xx/?vd_source=b989f2b109eb3b17e8178154a7de7a51
经典KMP算法，好好重温重温，KMP算法原理、最长相同前缀、next数组的求法、如何拿next数组寻找目标子串
class Solution {public int strStr(String haystack, String needle) {String momStr = haystack;String subStr = needle;if(subStr.length() == 0){return 0;}int[] next = new int[subStr.length()];getNext(next, subStr);int j = 0;for(int i = 0; i < momStr.length(); i++){while(j > 0 && subStr.charAt(j) != momStr.charAt(i)){j = next[j-1];}if(subStr.charAt(j) == momStr.charAt(i)){j++;}if(j == subStr.length()){return i - subStr.length() + 1;}}return -1;}public void getNext(int[] next, String subStr){int j = 0;next[0] = 0;for(int i = 1; i < subStr.length();i++){while(j > 0 && subStr.charAt(i) != subStr.charAt(j)){j = next[j-1];}if(subStr.charAt(i) == subStr.charAt(j)){j++;}next[i] = j;}}
}
LeetCode459 重复的子字符串
题目链接：https://leetcode.cn/problems/repeated-substring-pattern/description/
文章讲解：https://programmercarl.com/0459.重复的子字符串.html
视频讲解：https://www.bilibili.com/video/BV1cg41127fw/?vd_source=b989f2b109eb3b17e8178154a7de7a51
这题是看了Carl的讲解再做的，首先先使用KMP算法求出字符串的最长相同前后缀，再由此求得最长相等前后缀不包含的子串
根据一番充分性必要性的证明（具体证明在Carl哥的网站上）得到结论，如果字符串s是由重复子串构成，那么它的最长相等前后缀不包含的子串就是s的最小重复子串
接下来判断字符串s能否被它的最小重复子串的长度整除，如果能则说明它是由重复子串构成，否则则不是由重复子串构成
class Solution {public boolean repeatedSubstringPattern(String s) {int strLength = s.length();int[] next = new int[strLength];getNext(next, s);int minSubLength = strLength - next[strLength-1];if(next[strLength-1] > 0 && strLength % minSubLength == 0){return true;}else{return false;}}public void getNext(int[] next, String str){int j = 0;next[0] = 0;for(int i = 1;i < str.length();i++){while(j > 0 && str.charAt(i) != str.charAt(j)){j = next[j-1];}if(str.charAt(i) == str.charAt(j)){j++;}next[i] = j;}}
}