当前位置:网站首页>字符串的常见算法总结
字符串的常见算法总结
2020-11-06 01:18:00 【ClawHub的博客】
1、无重复字符的最长子串
3. 无重复字符的最长子串
滑动窗口解题。设置一个map来存储字符与其出现的位置,再定义窗口的开始与结束指针。
1 |
public static int lengthOfLongestSubstring(String s) { |
2、 最长公共子序列
1143. 最长公共子序列
涉及到两个字符串求子序列的问题,一般都是动态规划的范畴。难点就是要找到状态转换方程。
定义一个二维数组 dp 用来存储最长公共子序列的长度,其中 dp[i][j] 表示 S1 的前 i 个字符与 S2 的前 j 个字符最长公共子序列的长度。考虑 S1i 与 S2j 值是否相等,分为下面两种情况:
参考这个!!
1 |
public static int longestCommonSubsequence(String text1, String text2) { |
3、最长重复子数组
718. 最长重复子数组
动态规划问题:
1 |
public static int findLength(int[] A, int[] B) { |
4、字符串反转
使用两个指针。
1 |
public static void reverseString(char[] s) { |
5、字符串能否由字典中单词组成
给定一个字符串s和一个字典dict,判断字符串能否有字典中的字符串组成,字典中的字符串可以出现多次。例如s=“Ilovebytedance”,dict={“I”,“love”,“bytedance”}
用动态规划,dp[i]表示字符串s[0~i]是否可分的bool值。
字节跳动 单词拼接
139. 单词拆分
参考这里!!!
也是动态规划问题:
1 |
public static boolean wordBreak(String s, List<String> wordDict) { |
6、给定字符串的全排列
算法题解:给定一个字符串输出其全排列形式的所有字符串(JAVA代码)
字符串的全排列 Java实现
递归加回溯思想。
总结
字符串常见的算法解决思路好多都是动态规划问题。
版权声明
本文为[ClawHub的博客]所创,转载请带上原文链接,感谢
https://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/
边栏推荐
- ThreadLocal原理大解析
- Technical director, to just graduated programmers a word - do a good job in small things, can achieve great things
- 高级 Vue 组件模式 (3)
- 如何将分布式锁封装的更优雅
- Cocos Creator 原始碼解讀:引擎啟動與主迴圈
- 读取、创建和运行多个文件的3个Python技巧
- vite + ts 快速搭建 vue3 專案 以及介紹相關特性
- 10 easy to use automated testing tools
- 【QT】 QThread部分原始碼淺析
- 《Google軟體測試之道》 第一章google軟體測試介紹
猜你喜欢
随机推荐
6.7 theme resolver theme style parser (in-depth analysis of SSM and project practice)
03_ Detailed explanation and test of installation and configuration of Ubuntu Samba
如何对Pandas DataFrame进行自定义排序
xmppmini 專案詳解:一步一步從原理跟我學實用 xmpp 技術開發 4.字串解碼祕笈與訊息包
Listening to silent words: hand in hand teaching you sign language recognition with modelarts
如何使用ES6中的参数
6.9.2 session flashmapmanager redirection management
DevOps是什么
7.3.2 File Download & big file download
你的财务报告该换个高级的套路了——财务分析驾驶舱
Azure Data Factory(三)整合 Azure Devops 實現CI/CD
Anomaly detection method based on SVM
Ubuntu18.04上安裝NS-3
《Google軟體測試之道》 第一章google軟體測試介紹
词嵌入教程
如何在Windows Server 2012及更高版本中將域控制器降級
DRF JWT authentication module and self customization
Menu permission control configuration of hub plug-in for azure Devops extension
C language 100 question set 004 - statistics of the number of people of all ages
Polkadot series (2) -- detailed explanation of mixed consensus