資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理學
社會學
時尚
法學Java 程式求最長迴文子序列
對於最長迴文子序列，Java 程式碼如下 -
示例
public class Demo{
static String longest_seq(String str_1, String str_2){
int str_1_len = str_1.length();
int str_2_len = str_2.length();
char str_1_arr[] = str_1.toCharArray();
char str_2_arr[] = str_2.toCharArray();
int L[][] = new int[str_1_len + 1][str_2_len + 1];
for (int i = 0; i <= str_1_len; i++){
for (int j = 0; j <= str_2_len; j++){
if (i == 0 || j == 0){
L[i][j] = 0;
}
else if (str_1_arr[i - 1] == str_2_arr[j - 1]){
L[i][j] = L[i - 1][j - 1] + 1;
}
else{
L[i][j] = Math.max(L[i - 1][j], L[i][j - 1]);
}
}
}
int my_index = L[str_1_len][str_2_len];
char[] longest_seq = new char[my_index + 1];
int i = str_1_len, j = str_2_len;
while (i > 0 && j > 0){
if (str_1_arr[i - 1] == str_2_arr[j - 1]){
longest_seq[my_index - 1] = str_1_arr[i - 1];
i--;
j--;
my_index--;
}
else if (L[i - 1][j] > L[i][j - 1]){
i--;
} else {
j--;
}
}
String my_result = "";
for (int x = 0; x < longest_seq.length; x++){
my_result += longest_seq[x];
}
return my_result;
}
static String longestPalSubseq(String str){
String rev_str = str;
rev_str = reverse_str(rev_str);
return longest_seq(str, rev_str);
}
static String reverse_str(String str){
String my_result = "";
char[] trial = str.toCharArray();
for (int i = trial.length - 1; i >= 0; i--){
my_result += trial[i];
}
return my_result;
}
public static void main(String[] args){
String str = "HelloHelloo";
System.out.println("Longest palindromic subsequence is ");
System.out.println(longestPalSubseq(str));
}
}輸出
Longest palindromic subsequence is llell
一個名為 Demo 的類包含函式 'longest_seq'，它宣告兩個字串和兩個字元陣列。陣列將反覆迭代，並使用動態規劃技術找出最長的迴文序列。在此方法中，一旦找到特定陣列的值，它就會被儲存起來，而不是重新計算，從而使計算更有效率。
一個名為 'longestPalSubseq' 的函式將字串作為引數，並反轉該字串並透過傳遞反轉後的字串來呼叫 'longest_seq' 函式。另一個名為 'reverse_str' 的函式用於反轉作為引數傳遞給該函式的字串。在主函式中，字串被定義，並呼叫 ‘longestPalSubseq’ 函式，並在控制檯上顯示輸出。
更新於: 17-Aug-2020
179 瀏覽量
廣告