This post first appeared on my personal blog: Tail-tail-fall
1. The KMP algorithm
When it comes to the string problem, the KMP algorithm has to be mentioned. It is used to solve the problem of string search. You can find the position of a substring (W) in a string (S). The KMP algorithm reduces the time complexity of character matching to O(m+ N) and the space complexity to O(m). Because the method of “violent search” will backtrack the main string repeatedly, resulting in low efficiency, while THE KMP algorithm can make use of the valid information that has been partially matched to keep the pointer on the main string from backtracking, and make the pattern string move to the effective position as much as possible by modifying the pointer of the substring.
Please refer to:
- String matching KMP algorithm
- Understand KMP from start to finish
- How to better understand and master KMP algorithm?
- KMP algorithm detailed analysis
- Graphic KMP algorithm
- KMP String Matching Algorithm that Even Wang Can Understand
- KMP string matching algorithm 1
1.1 BM algorithm
BM algorithm is also an exact string matching algorithm, which uses the method of right-to-left comparison and applies two heuristic rules, namely bad character rules and suffix rules, to determine the jump distance to the right. The basic idea is to match characters from right to left. If a character does not match, find a maximum right-shifted value from the bad character table and the suffix table, and move the pattern string right to continue matching. String matching KMP algorithm
2. Replace Spaces
Implement a function that replaces each space in a string with “%20”. For example, if the string is “We Are Happy.”, the replacement string is “We%20Are%20Happy”.
public class Solution {
public String replaceSpace(StringBuffer str) {
StringBuffer res = new StringBuffer();
int len = str.length() - 1;
for(int i = len; i >= 0; i--){
if(str.charAt(i) == ' ')
res.append("02%");
else
res.append(str.charAt(i));
}
returnres.reverse().toString(); }}Copy the code3. Longest public prefix
Write a function to find the longest public prefix in an array of strings. Returns the empty string “” if no public prefix exists.
class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0)
return "";
Arrays.sort(strs);
char [] first = strs[0].toCharArray();
char [] last = strs[strs.length - 1].toCharArray();
StringBuffer res = new StringBuffer();
int len = first.length < last.length ? first.length : last.length;
int i = 0;
while(i < len){
if(first[i] == last[i]){
res.append(first[i]);
i++;
}
else
break;
}
returnres.toString(); }}Copy the code4. Longest palindrome string
Given a string of uppercase and lowercase letters, find the longest palindrome string constructed from these letters. Pay attention to case sensitivity during construction. For example, “Aa” cannot be treated as a palindrome string.
class Solution {
public int longestPalindrome(String s) {
HashSet<Character> hs = new HashSet<>();
int len = s.length();
int count = 0;
if(len == 0)
return 0;
for(int i = 0; i<len; i++){
if(hs.contains(s.charAt(i))){
hs.remove(s.charAt(i));
count++;
}else{ hs.add(s.charAt(i)); }}return hs.isEmpty() ? count * 2 : count * 2 + 1; }}Copy the code4.1 Verifying palindrome strings
Given a string, verify that it is a palindrome string. Only alphanumeric characters are considered, regardless of the case of the letters. Note: In this case, we define an empty string as a valid palindrome string.
Two Pointers compare head to tail. Note that only alphanumeric characters are considered and the case of letters can be ignored.
class Solution {
public boolean isPalindrome(String s) {
if(s.length() == 0)
return true;
int l = 0, r = s.length() - 1;
while(l < r){
if(! Character.isLetterOrDigit(s.charAt(l))){ l++; }else if(! Character.isLetterOrDigit(s.charAt(r))){ r--; }else{
if(Character.toLowerCase(s.charAt(l)) ! = Character.toLowerCase(s.charAt(r)))return false; l++; r--; }}return true; }}Copy the code4.2 Longest callback substring
Given a string s, find the longest substring in s. You can assume that the maximum length of s is 1000.
class Solution {
private int index, len;
public String longestPalindrome(String s) {
if(s.length() < 2)
return s;
for(int i = 0; i < s.length()-1; i++){
PalindromeHelper(s, i, i);
PalindromeHelper(s, i, i+1);
}
return s.substring(index, index+len);
}
public void PalindromeHelper(String s, int l, int r){
while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){
l--;
r++;
}
if(len < r - l - 1){
index = l + 1;
len = r - l - 1; }}}Copy the code4.3 Longest sequence of rhymes
Given a string s, find the longest sequence of subroutines. We can assume that the maximum length of s is 1000. The difference between the longest subroutine sequence and the longest subroutine in the previous problem is that a subsequence is a sequence of contiguous characters in a string, whereas a subsequence is a sequence of characters in a string that hold relative positions. For example, “BBBB” can make a subsequence of the string “bbbab” but not a substring.
class Solution {
public int longestPalindromeSubseq(String s) {
int len = s.length();
int [][] dp = new int[len][len];
for(int i = len - 1; i>=0; i--){
dp[i][i] = 1;
for(int j = i+1; j < len; j++){
if(s.charAt(i) == s.charAt(j))
dp[i][j] = dp[i+1][j-1] + 2;
else
dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); }}return dp[0][len-1]; }}Copy the code5. String arrangement
Given two strings s1 and s2, write a function to determine whether S2 contains a permutation of s1. In other words, one of the permutations of the first string is a substring of the second string.
class Solution {
public boolean checkInclusion(String s1, String s2) {
int l1 = s1.length();
int l2 = s2.length();
int [] count = new int [128];
if(l1 > l2)
return false;
for(int i = 0; i<l1; i++){
count[s1.charAt(i) - 'a'] + +; count[s2.charAt(i) -'a']--;
}
if(allZero(count))
return true;
for(int i = l1; i<l2; i++){
count[s2.charAt(i) - 'a']--;
count[s2.charAt(i-l1) - 'a'] + +;if(allZero(count))
return true;
}
return false;
}
public boolean allZero(int [] count){
int l = count.length;
for(int i = 0; i < l; i++){
if(count[i] ! =0)
return false;
}
return true; }}Copy the code6. Print the full array of strings
Enter a string and print out all the permutations of the characters in the string in lexicographical order. For example, if you enter the string ABC, you print out all the strings ABC, ACb, BAC, BCA, CAB, and CBA that can be arranged by characters A, B, and C.
Break the problem down into simple steps: The first step is to find all the characters that can appear in the first position (that is, swap the first character with all the characters that follow); The second step is to fix the first character and find the arrangement of all the following characters. At this point, you can split all subsequent characters into two parts (the first character and all remaining characters), and so on. So, we can do this recursively.
public class Solution {
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> Permutation(String str) {
if(str == null)
return res;
PermutationHelper(str.toCharArray(), 0);
Collections.sort(res);
return res;
}
public void PermutationHelper(char[] str, int i){
if(i == str.length - 1){
res.add(String.valueOf(str));
}else{
for(int j = i; j < str.length; j++){
if(j! =i && str[i] == str[j])continue;
swap(str, i, j);
PermutationHelper(str, i+1); swap(str, i, j); }}}public void swap(char[] str, int i, int j) {
chartemp = str[i]; str[i] = str[j]; str[j] = temp; }}Copy the code7. The first character that appears only once
Finger offer: the first once-occurrence character finds the first once-occurrence character in a string (0<= string length <=10000, all letters) and returns its position, or -1 if not.
First, count the number of occurrences of each letter in the hash table, and then scan the second time to obtain the number of entries in the hash table. You can also use arrays instead of hash tables.
import java.util.HashMap;
public class Solution {
public int FirstNotRepeatingChar(String str) {
int len = str.length();
if(len == 0)
return -1;
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < len; i++){
if(map.containsKey(str.charAt(i))){
int value = map.get(str.charAt(i));
map.put(str.charAt(i), value+1);
}else{
map.put(str.charAt(i), 1); }}for(int i = 0; i < len; i++){
if(map.get(str.charAt(i)) == 1)
return i;
}
return -1; }}Copy the code8. Flip the word order column
Sword finger offer: flip word order column LeetCode: flip word in string
Trim () and split() are easy to do
public class Solution {
public String reverseWords(String s) {
if(s.trim().length() == 0)
return s.trim();
String [] temp = s.trim().split("+");
String res = "";
for(int i = temp.length - 1; i > 0; i--){
res += temp[i] + "";
}
return res + temp[0]; }}Copy the code9. Rotate the string
Leetcode: Rotate string given two strings, A and B. The rotation operation of A moves the leftmost character of A to the rightmost. For example, if A = ‘abcde’, the result is ‘bcdea’ after one move. Returns True if A can become B after A number of rotations.
class Solution {
public boolean rotateString(String A, String B) {
returnA.length() == B.length() && (A+A).contains(B); }}Copy the code9.1 Left-rotate string
A simple task in assembly language is to simulate the result of a shift instruction called cyclic left shift (ROL) with a string. For a given character sequence S, you loop the sequence output K bits to the left. For example, the character sequence S= “abcXYZdef” requires that the output loop be shifted three bits to the left, i.e., “XYZdefabc”. Isn’t that easy? OK, fix it!
A cut is made after the NTH character to split the string into two parts and rejoin them. Note that the string length is 0.
public class Solution {
public String LeftRotateString(String str,int n) {
int len = str.length();
if(len == 0)
return "";
n = n % len;
String s1 = str.substring(n, len);
String s2 = str.substring(0, n);
returns1+s2; }}Copy the code9.2 Reversing the Character String
Write a function that inverts the input string.
class Solution {
public String reverseString(String s) {
if(s.length() < 2)
return s;
int l = 0, r = s.length() - 1;
char [] strs = s.toCharArray();
while(l < r){
char temp = strs[l];
strs[l] = strs[r];
strs[r] = temp;
l++;
r--;
}
return newString(strs); }}Copy the code10. Convert strings to integers
A library function that converts a string to an Integer (implements integer.valueof (string), but returns 0 if string does not meet numeric requirements), requiring that strings cannot be used to convert integers. Returns 0 if the value is 0 or the string is not a valid value.
public class Solution {
public int StrToInt(String str) {
if(str.length() == 0)
return 0;
int flag = 0;
if(str.charAt(0) = ='+')
flag = 1;
else if(str.charAt(0) = =The '-')
flag = 2;
int start = flag > 0 ? 1 : 0;
long res = 0;
while(start < str.length()){
if(str.charAt(start) > '9' || str.charAt(start) < '0')
return 0;
res = res * 10 + (str.charAt(start) - '0');
start ++;
}
return flag == 2? - (int)res : (int)res; }}Copy the code11. Regular expression matching
Implement a function to match regular expressions including ‘. ‘and’ * ‘. The character ‘. ‘in the pattern represents any character, and the character’ * ‘indicates that the character preceding it can occur any number of times (including 0). In this case, matching means that all characters in a string match the entire pattern. For example, the string “aaa” matches the patterns “A.a” and “ab*ac*a”, but not “aa.a” and “ab*a”
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length()+1][p.length()+1];
dp[0] [0] = true;
for (int j = 0; i < p.length(); j++) {
if (p.charAt(j) == The '*' && dp[0][j-1]) {
dp[0][j+1] = true; }}for (int i = 0 ; i < s.length(); i++) {
for (int j = 0; j < p.length(); j++) {
if (p.charAt(j) == '. ') {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == s.charAt(i)) {
dp[i+1][j+1] = dp[i][j];
}
if (p.charAt(j) == The '*') {
if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '. ') {
dp[i+1][j+1] = dp[i+1][j-1];
} else {
dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]); }}}}return dp[s.length()][p.length()];
}
Copy the code12. A numeric string
Implement a function to determine if a string represents a number (both integer and decimal). For example, + 100 “string”, “5 e2”, “- 123”, “3.1416” and “1 e – 16” numerical value. But “12e”, “1A3.14”, “1.2.3”, “+-5” and “12E +4.3” are not.
Set three identifiers to record “+/-“, “e/E” and “respectively. Whether or not.
public class Solution {
public boolean isNumeric(char[] str) {
int len = str.length;
boolean sign = false, decimal = false, hasE = false;
for(int i = 0; i < len; i++){
if(str[i] == '+' || str[i] == The '-') {if(! sign && i >0 && str[i-1] != 'e' && str[i-1] != 'E')
return false;
if(sign && str[i-1] != 'e' && str[i-1] != 'E')
return false;
sign = true;
}else if(str[i] == 'e' || str[i] == 'E') {if(i == len - 1)
return false;
if(hasE)
return false;
hasE = true;
}else if(str[i] == '. ') {if(hasE || decimal)
return false;
decimal = true;
}else if(str[i] < '0' || str[i] > '9')
return false;
}
return true; }}Copy the code13. The first non-repeating character in a character stream
Implement a function to find the first character in a character stream that occurs only once. For example, when only the first two characters “go” are read from the character stream, the first character that appears only once is “g”. When the first six characters “Google” are read from this character stream, the first character that appears only once is “L”.
A hash table is used to store each character and the number of occurrences, and a string S is used to store the order of characters in the character stream.
import java.util.HashMap;
public class Solution {
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
StringBuffer s = new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch)
{
s.append(ch);
if(map.containsKey(ch)){
map.put(ch, map.get(ch)+1);
}else{
map.put(ch, 1); }}//return the first appearence once char in current stringstream
public char FirstAppearingOnce(a)
{
for(int i = 0; i < s.length(); i++){
if(map.get(s.charAt(i)) == 1)
return s.charAt(i);
}
return The '#'; }}Copy the code