目录
  1. 1、无重复字符的最长子串
  2. 2、 最长公共子序列
  3. 3、最长重复子数组
  4. 4、字符串反转
  5. 5、字符串能否由字典中单词组成
  6. 6、给定字符串的全排列
  7. 总结
字符串的常见算法总结

1、无重复字符的最长子串

3. 无重复字符的最长子串
滑动窗口解题。设置一个map来存储字符与其出现的位置,再定义窗口的开始与结束指针。

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) {
//边界检查
if (s == null || s.isEmpty()) {
return 0;
}
//结果
int res = 0;
//定义一个map,key存放不重复的字符,val为字符的位置
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、 最长公共子序列

1143. 最长公共子序列
涉及到两个字符串求子序列的问题,一般都是动态规划的范畴。难点就是要找到状态转换方程。
定义一个二维数组 dp 用来存储最长公共子序列的长度,其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等,分为下面两种情况:
参考这个!!

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) {
//边界检查
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];
//状态转移方程
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、最长重复子数组

718. 最长重复子数组
动态规划问题:

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) {
//边界检查
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、字符串反转

使用两个指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void reverseString(char[] s) {
//边界检查
if (s.length <= 1) {
return;
}
//双指针法
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
}

5、字符串能否由字典中单词组成

给定一个字符串s和一个字典dict,判断字符串能否有字典中的字符串组成,字典中的字符串可以出现多次。例如s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
用动态规划,dp[i]表示字符串s[0~i]是否可分的bool值。
字节跳动 单词拼接
139. 单词拆分
参考这里!!!
也是动态规划问题:

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、给定字符串的全排列

算法题解:给定一个字符串输出其全排列形式的所有字符串(JAVA代码)
字符串的全排列 Java实现
递归加回溯思想。

总结

字符串常见的算法解决思路好多都是动态规划问题。

tencent.jpg

文章作者: ClawHub
文章链接: https://www.clawhub.club/posts/2020/01/06/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ClawHub的博客
打赏
  • 微信
  • 支付宝
扫一扫关注ClawHub公众号,专注Java、技术分享、面试资源。