最长公共子串问题的java版计算
星期三, 2023-05-17 | Author: Lee | algorithm-learn, JAVA-and-J2EE, linux | 1,313 views
1.最长公共子串问题
【题目】给定两个字符串str1和str2,返回两个字符串的最长公共子串。
【举例】str1="1AB2345CD",str2="12345EF",返回"2345"。
【要求】如果 str1 长度为 M,str2 长度为N,实现时间复杂度为 O(M×N),额外空间复杂度为 O(1)的方法。
【难度】3星
/** * * 1.最长公共子串问题 【题目】给定两个字符串str1和str2,返回两个字符串的最长公共子串。 * 【举例】str1="1AB2345CD",str2="12345EF",返回"2345"。 【要求】如果 str1 长度为 M,str2 长度为 * N,实现时间复杂度为 O(M×N),额外空间复杂度为 O(1)的方法。 【难度】3星 * * @author sara * */ public class MaxSubStr { public static void main(String[] args) { String str1="1AB2345CD",str2="12345EF"; String str = getMaxSub(str1,str2); System.out.println(str); } public static String getMaxSub(String s1, String s2) { String sStr = s1, mStr = s2; if (s1.length() > s2.length()) { sStr = s2; mStr = s1; } String str = ""; for (int i = 0; i < sStr.length(); i++) { for (int j = 1; j < sStr.length() - i; j++) { if (mStr.contains(sStr.substring(i, i + j)) && j > str.length()) { str = sStr.substring(i, i + j); } } } return str; } public static void getDp(char[] str1, char[] str2) { } } |
文章作者: Lee
本文地址: https://www.pomelolee.com/2398.html
除非注明,Pomelo Lee文章均为原创,转载请以链接形式标明本文地址
No comments yet.
Leave a comment
Search
相关文章
热门文章
最新文章
文章分类
- ajax (10)
- algorithm-learn (3)
- Android (6)
- as (3)
- computer (85)
- Database (30)
- disucz (4)
- enterprise (1)
- erlang (2)
- flash (5)
- golang (3)
- html5 (18)
- ios (4)
- JAVA-and-J2EE (186)
- linux (143)
- mac (10)
- movie-music (11)
- pagemaker (36)
- php (50)
- spring-boot (2)
- Synology群晖 (2)
- Uncategorized (6)
- unity (1)
- webgame (15)
- wordpress (33)
- work-other (2)
- 低代码 (1)
- 体味生活 (40)
- 前端 (21)
- 大数据 (8)
- 游戏开发 (9)
- 爱上海 (19)
- 读书 (4)
- 软件 (3)