最长公共子串问题的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) {
 
	}
 
}

Tags:

文章作者: Lee

本文地址: https://www.pomelolee.com/2398.html

除非注明,Pomelo Lee文章均为原创,转载请以链接形式标明本文地址

No comments yet.

Leave a comment

Search

相关文章

文章分类

Links

Meta