当前位置:网站首页>Summary of common string algorithms

Summary of common string algorithms

2020-11-06 01:18:16 Clamhub's blog

1、 Longest substring without repeating characters

3. Longest substring without repeating characters
Slide the window to solve the problem . Set up a map To store characters and where they appear , Redefine the start and end pointer of the window .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int lengthOfLongestSubstring(String s) {
// Boundary check
if (s == null || s.isEmpty()) {
return 0;
}
// result
int res = 0;
// Define a map,key Store characters that don't repeat ,val For the position of the character
Map<Character, Integer> map = new HashMap<>();
for (int start = 0, end = 0; end < s.length(); end++) {
char c = s.charAt(end);
if (map.containsKey(c)) {
start = Math.max(map.get(c), start);
}
res = Math.max(end - start + 1, res);
map.put(c, end + 1);
}
return res;
}

2、 Longest common subsequence

1143. Longest common subsequence
It involves the problem of finding subsequences of two strings , Generally, it is the category of dynamic programming . The difficulty is to find the state transition equation .
Define a two-dimensional array dp The length used to store the longest common subsequence , among dp[i][j] Express S1 Before i Characters and S2 Before j The length of the longest common subsequence of characters . consider S1i And S2j Whether the values are equal , It can be divided into the following two situations :
Refer to this !!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  public static int longestCommonSubsequence(String text1, String text2) {
// Boundary check
if (text1 == null || text1.isEmpty()) {
return 0;
}
if (text2 == null || text2.isEmpty()) {
return 0;
}
int n1 = text1.length(), n2 = text2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// State transition equation
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
}
return dp[n1][n2];
}

3、 Longest repeating subarray

718. Longest repeating subarray
Dynamic programming problem :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int findLength(int[] A, int[] B) {
// Boundary check
if (A.length <= 0 || B.length <= 0) {
return 0;
}
int result = 0;
int n = A.length;
int m = B.length;
int[][] dp = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (A[i - 1] == B[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
result = Math.max(result, dp[i][j]);
}
}
}
return result;
}

4、 String inversion

Using two Pointers .

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void reverseString(char[] s) {
// Boundary check
if (s.length <= 1) {
return;
}
// Double finger needling
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
}

5、 Can a string consist of words in a dictionary

Given a string s And a dictionary dict, Determine whether a string can be composed of strings in a dictionary , A string in a dictionary can appear more than once . for example s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
With dynamic programming ,dp[i] Representation string s[0~i] Whether it is separable bool value .
Bytes to beat Word splicing
139. Word splitting
Reference resources here !!!
It's also a dynamic programming problem :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 public static boolean wordBreak(String s, List<String> wordDict) {
Set<String> wordDictSet = new HashSet(wordDict);
boolean[] dp = new boolean[s.length() + 1];
dp[0] = true;
for (int i = 1; i <= s.length(); i++) {
for (int j = 0; j < i; j++) {
if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[s.length()];
}

6、 A full permutation of a given string

Algorithm problem solution : Given a string, output all strings in its full permutation form (JAVA Code )
The full permutation of strings Java Realization
The idea of recursion and backtracking .

summary

Most of the common string algorithms are dynamic programming problems .

tencent.jpg

版权声明
本文为[Clamhub's blog]所创,转载请带上原文链接,感谢

随机推荐