The title quick reference
With a link to Leetcode
-
- Inverted string
-
- Reverse string II
- Offer 05. Replace the blank
-
- Flip the word in the string
- Finger at offer58-ii. Rotate string left
- 28. Achieve strStr ()
-
- Repeated substrings
Subtopic interpretation
If the key part of the problem can be solved directly by using library functions, it is recommended not to use library functions
Consider using library functions if they are only a small part of the process and you already know the inner workings of the library function.
public void reverseString(char[] s) {
int head = 0;
int end = s.length - 1;
char tmp;
while(head < end){ tmp = s[end]; s[end] = s[head]; s[head] = tmp; head++; end--; }}Copy the code541 Reverse string II
class Solution {
public String reverseStr(String s, int k) {
char[] arr = s.toCharArray();
int len = s.length();
int head = 0;
int last = 2 * k - 1;
while (last <= len - 1){
reverse(head, head + k - 1, arr);
last += 2 * k;
head += 2 * k;
}
int end = (len - 1 - head < k) ? len - 1 : head + k - 1;
reverse(head, end, arr);
return String.valueOf(arr);
}
public void reverse(int first, int end, char[] arr){
while (first < end){
chartmp = arr[first]; arr[first] = arr[end]; arr[end] = tmp; first++; end--; }}}Copy the codePlan before you plan
- Enough for 2 k
Exchange function
- Not enough 2 k
Less than k– the commutative function is greater than k, less than 2k– the commutative function
The sword means Offer5 instead of space
class Solution {
public String replaceSpace(String s) {
// Using StringBuffer single thread is faster
StringBuffer stb = new StringBuffer();
for (int i = 0; i < s.length(); i++) {
char point = s.charAt(i);
if (point == ' '){
stb.append("% 20");
}else{ stb.append(point); }}returnstb.toString(); }}Copy the codeHere is another way to think about it: 1. You can expand the space of the original string to accommodate new characters. Locate the last character of the original string. 3. Locate the last character of the new string. Compare the copy
public String replaceSpace(String s) {
if(s == null || s.length() == 0) {return s;
}
// Expand the space with twice the number of Spaces
StringBuilder str = new StringBuilder();
for (int i = 0; i < s.length(); i++) {
if(s.charAt(i) == ' '){
str.append(""); }}// Return if there is no space
if(str.length() == 0) {return s;
}
// Define two Pointers with Spaces
int left = s.length() - 1;// Left pointer: points to the last position of the original string
s += str.toString();
int right = s.length()-1;// Right pointer: points to the last position of the extension string
char[] chars = s.toCharArray();
while(left>=0) {if(chars[left] == ' '){
chars[right--] = '0';
chars[right--] = '2';
chars[right] = The '%';
}else{
chars[right] = chars[left];
}
left--;
right--;
}
return new String(chars);
}
Copy the code151. Flip the words in the string method one: the comparison of water, using the split function in the string, additional O (N) space, finally strung together, to note that removes white Spaces at the last, and there exists continuous separator when two Spaces, for example, after the split is “, “use. The equals () method: The final time complexity of reversing all characters, and finally reversing the words, is O(1). Do this step by step, initially removing extra Spaces. Reverse all strings. Reverse the words.
/ / method
public static String reverseWords(String s) {
String[] s1 = s.split("");
StringBuffer stb = new StringBuffer();
for (int i = s1.length - 1; i >= 0; i--){
if(! s1[i].equals("")) {
stb.append(s1[i] + ""); }}// Remove the last space
return stb.toString().substring(0,stb.length() - 1);
}
public static void main(String[] args) {
System.out.println(reverseWords("We are happy"));//happy are We
}
Copy the code2 / / method
class Solution {
/** ** does not use Java built-in methods * * 1. 2. Invert the entire string * 3. Invert individual words */
public String reverseWords(String s) {
// System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
// 1. Remove extra space at the beginning, end, and middle
StringBuilder sb = removeSpace(s);
// 2. Invert the entire string
reverseString(sb, 0, sb.length() - 1);
// 3. Reverse the words
reverseEachWord(sb);
return sb.toString();
}
private StringBuilder removeSpace(String s) {
// System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
int start = 0;
int end = s.length() - 1;
while (s.charAt(start) == ' ') start++;
while (s.charAt(end) == ' ') end--;
StringBuilder sb = new StringBuilder();
while (start <= end) {
char c = s.charAt(start);
if(c ! =' ' || sb.charAt(sb.length() - 1) != ' ') {
sb.append(c);
}
start++;
}
// System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
return sb;
}
/** * inverts the character */ of the interval specified by [start, end]
public void reverseString(StringBuilder sb, int start, int end) {
// System.out.println("ReverseWords.reverseString() called with: sb = [" + sb + "], start = [" + start + "], end = [" + end + "]");
while (start < end) {
char temp = sb.charAt(start);
sb.setCharAt(start, sb.charAt(end));
sb.setCharAt(end, temp);
start++;
end--;
}
// System.out.println("ReverseWords.reverseString returned: sb = [" + sb + "]");
}
private void reverseEachWord(StringBuilder sb) {
int start = 0;
int end = 1;
int n = sb.length();
while (start < n) {
while(end < n && sb.charAt(end) ! =' ') {
end++;
}
reverseString(sb, start, end - 1);
start = end + 1;
end = start + 1; }}}Copy the codeFinger at offer58-ii. Rotate string leftIn fact, the time complexity of using substr is the same as that of reversing, both are O(n), but the space complexity of using substr is O(n), while the space complexity of reversing method is O(1). Substring = substring; substring = substring;
/ / method one:
public String reverseLeftWords(String s, int n) {
StringBuilder sb = new StringBuilder();
sb.append(s.substring(n)+s.substring(0,n));
return sb.toString();
}
/ / method 2:
class Solution {
public String reverseLeftWords(String s, int n) {
int len=s.length();
StringBuilder sb=new StringBuilder(s);
reverseString(sb,0,n-1);
reverseString(sb,n,len-1);
return sb.reverse().toString();
}
public void reverseString(StringBuilder sb, int start, int end) {
while (start < end) {
chartemp = sb.charAt(start); sb.setCharAt(start, sb.charAt(end)); sb.setCharAt(end, temp); start++; end--; }}}Copy the code28 implementation of strStr() violent solution must not work, there is a good API, is the KMP algorithm, very important, it is recommended to memorize the KMP algorithm
public static int strStr(String haystack, String needle) {
if (needle.equals("")) return 0;// Every topic has its own requirements
if (haystack.length() == 0 || needle.length() == 0 || haystack.length() < needle.length()) return -1;
char[] str1 = haystack.toCharArray();
char[] str2 = needle.toCharArray();
// Create the next[I] array, stored before the i-th character of str2, the longest (prefix and suffix equal) length. Note that the string itself is not included
int[] next = new int[str2.length];
next[0] = -1;
if (str2.length > 1) {// Prevent str2 from having only one character
next[1] = 0;
}
int i = 2;
Next [i-1] = 0, cn = 0; next[i-1] = 0;
int cn = 0;
while (i < str2.length){
if (str2[i - 1] == str2[cn]){
next[i++] = ++cn;
}else if (cn == 0){
next[i++] = 0;
}else{ cn = next[cn]; }}// Use next[] array to solve string matching problem
int t1 = 0; int t2 = 0;
while (t1 < str1.length && t2 < str2.length){
if (str1[t1] == str2[t2]){
t1++;
t2++;
}else if (t2 == 0){
t1++;
}else{ t2 = next[t2]; }}return t2 == str2.length ? t1 - t2 : -1;
}
public static void main(String[] args) {
String haystack = "abcdeabcfee";
String needle = "d";
System.out.println(strStr(haystack,needle));
}
Copy the code29. Repeated substringsI didn’t know I was going to use KMP at first, but because I’m looking for repetitive strings, next[]’s array is definitely regular. You can run several next[] arrays to see what the pattern looks like:
public static boolean repeatedSubstringPattern(String s) {
if (s.length() < 2) return false;
// We can use the KMP algorithm to assume that the next[] array must have corresponding rules
char[] arr = s.toCharArray();
int n = s.length();
int[] next = new int[n + 1];
next[0] = -1;
next[1] = 0;
int i = 2;
int cn = 0;
while (i <= n){
if (arr[i - 1] == arr[cn]){
next[i++] = ++cn;
}else if (cn == 0){
next[i++] = 0;
}else{ cn = next[cn]; }}for (int h : next){
System.out.println(h);
}
if(next[n] ! =0 && n % (n - (next[n])) == 0) {return true;
}
return false;
}
public static void main(String[] args) {
String haystack = "abcabcabc";
System.out.println(repeatedSubstringPattern(haystack));
}
Copy the codeconclusion
- It is recommended not to use library functions if the key parts of the problem can be solved directly. Consider using library functions if they are only a small part of the process and you already know the inner workings of the library function.
- Double Pointers are common in arrays, linked lists, and strings. Many array fill class problems, you can first expand the size of the array after the fill, and then operate from back to front
- When you need to fix the rules for processing strings paragraph by paragraph, think of working on a for loop expression with the following idea: global inversion then local inversion, local inversion then global inversion
- The main idea of KMP is that when a string mismatch occurs, you can know a portion of the text that has already been matched, and you can use this information to avoid having to do the match all over again. —- the most important algorithm in the string