輸入一個字符串s攘蔽,我們可以刪除字符串s中的任意字符,讓剩下的字符串形成一個對稱字符串呐粘,且該字符串為最長對稱字符串满俗。如:輸入google,則找到最長對稱字符串為goog作岖;如輸入abcda則能找到3個最長對稱字符串為aba/aca/ada唆垃。 若最長對稱字符串存在多個,則輸出多個相同長度的最長對稱字符串痘儡,且字符串中不包含特殊字符辕万。
import java.util.HashSet;
import java.util.Set;
import java.util.regex.Pattern;
/**
* @author sunlichao on 2019-07-09.
*/
public class Test1 {
/**
* 根據(jù)特殊字符進行字符串分割
* @param str 輸入字符串
* @return
*/
private static String[] stringFilter(String str) {
String regEx = "[^a-zA-Z0-9]";
Pattern p = Pattern.compile(regEx);
return p.split(str);
}
/**
* 遍歷生成的二維數(shù)組,遞歸查找最長路徑
* @param a 第一個字符串
* @param b 第二個字符串
* @param mux 二維中間數(shù)組
* @param i 二維數(shù)組raw位置
* @param j 二維數(shù)組column位置
* @param path 一次查找的字符串
* @param paths 最終結(jié)果集合
*/
private static void getAllLcs( String a, String b, int[][] mux, int i, int j, String path, Set<String> paths) {
StringBuilder pathBuilder = new StringBuilder(path);
while (i > 0 && j > 0) {
if (a.charAt(i - 1) == b.charAt(j - 1)) {
pathBuilder.append(a.charAt(i - 1));
--i;
--j;
}else {
if (mux[i - 1][j] > mux[i][j - 1]) {
--i;
} else if (mux[i - 1][j] < mux[i][j - 1]) {
--j;
} else {
getAllLcs(a, b, mux, i - 1, j, pathBuilder.toString(), paths);
getAllLcs(a, b, mux, i, j - 1, pathBuilder.toString(), paths);
return;
}
}
}
paths.add(pathBuilder.toString());
}
/**
* 字符串s,我們可以刪除字符串s中的任意字符渐尿,讓剩下的字符串形成一個對稱字符串醉途,且該字符串為最長對稱字符串。
* 原字符串反轉(zhuǎn)砖茸,成為查找最大公共子序列問題
* @param input 待查找字符串
* @return 查找結(jié)果
*/
private static String findLCS(String input) {
if (input == null || input.length() == 0) {
return "";
}
// 將字符串反轉(zhuǎn)
String reverse = new StringBuilder(input).reverse().toString();
// 字符串長度
int len = input.length();
// 矩陣 -> 二維數(shù)組隘擎,第一行與第一列皆為零,兩個原因凉夯,一是方便算法越界處理货葬,二是在
// 通過矩陣查找子串時,作為終止時間判斷使用劲够。
int[][] tmp = new int[len + 1][len + 1];
for (int i = 1; i < len + 1; i++) {
for (int j = 1; j < len + 1; j++) {
if (input.charAt(i - 1) == reverse.charAt(j - 1)) {
//取值為左上角值+1
tmp[i][j] = tmp[i - 1][j - 1] + 1;
} else {
//取值為左/上最大值震桶,通過矩陣值反向查找路徑時,同一子串會有多個征绎。
tmp[i][j] = Math.max(tmp[i - 1][j], tmp[i][j - 1]);
}
}
}
// 查找路徑時蹲姐,存在多個路徑是一個字符串的情況,set去重人柿。
Set<String> paths = new HashSet<>();
Test1.getAllLcs(input, reverse, tmp, input.length(), reverse.length(), "", paths);
return String.join("/", paths);
}
/**
* 包括對特殊字符柴墩,結(jié)果格式生成
* @param input 待處理字符串
* @return
*/
public static String maxs(String input) {
String[] prepare = stringFilter(input);
StringBuffer sb = new StringBuffer();
for (String str : prepare) {
String result = findLCS(str);
sb.append(result);
sb.append("/");
}
return sb.substring(0, sb.length()-1);
}
public static void main(String[] args) {
// TODO 輸出最長對稱字符串:goog
String input1 = "google";
System.out.println(maxs(input1));
// TODO 輸出3個最長對稱字符串:aba/aca/ada
String input2 = "abcda";
System.out.println(maxs(input2));
// TODO 輸出2個最長對稱字符串:pop/upu,不會輸出特殊字符的對稱字符串p-p
String input3 = "pop-upu";
System.out.println(maxs(input3));
}
}
參考:
https://segmentfault.com/q/1010000014740633?_ea=14643174
動態(tài)規(guī)劃 最長公共子序列(LCS) 過程圖解
https://blog.csdn.net/u012426298/article/details/82796660
https://blog.csdn.net/afei__/article/details/83153399