Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita19d8b2

Browse files
authored
Merge pull requestTheAlgorithms#1713 from matteomessmer/LongestPalindromicSubsequence
Fixes:TheAlgorithms#1709 Longest palindromic subsequence
2 parentsd7a5dbe +60c0291 commita19d8b2

File tree

2 files changed

+90
-0
lines changed

2 files changed

+90
-0
lines changed
Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
packagetest;
2+
importjava.lang.*;
3+
importjava.io.*;
4+
importjava.util.*;
5+
6+
/**
7+
* Algorithm explanation https://www.educative.io/edpresso/longest-palindromic-subsequence-algorithm
8+
*/
9+
publicclassLongestPalindromicSubsequence {
10+
publicstaticvoidmain(String[]args) {
11+
Stringa ="BBABCBCAB";
12+
Stringb ="BABCBAB";
13+
14+
StringaLPS =LPS(a);
15+
StringbLPS =LPS(b);
16+
17+
System.out.println(a +" => " +aLPS);
18+
System.out.println(b +" => " +bLPS);
19+
}
20+
21+
publicstaticStringLPS(Stringoriginal)throwsIllegalArgumentException {
22+
StringBuilderreverse =newStringBuilder(original);
23+
reverse =reverse.reverse();
24+
returnrecursiveLPS(original,reverse.toString());
25+
}
26+
27+
privatestaticStringrecursiveLPS(Stringoriginal,Stringreverse) {
28+
StringbestResult ="";
29+
30+
//no more chars, then return empty
31+
if(original.length() ==0 ||reverse.length() ==0) {
32+
bestResult ="";
33+
}else {
34+
35+
//if the last chars match, then remove it from both strings and recur
36+
if(original.charAt(original.length() -1) ==reverse.charAt(reverse.length() -1)) {
37+
StringbestSubResult =recursiveLPS(original.substring(0,original.length() -1),reverse.substring(0,reverse.length() -1));
38+
39+
bestResult =reverse.charAt(reverse.length() -1) +bestSubResult;
40+
}else {
41+
//otherwise (1) ignore the last character of reverse, and recur on original and updated reverse again
42+
//(2) ignore the last character of original and recur on the updated original and reverse again
43+
//then select the best result from these two subproblems.
44+
45+
StringbestSubResult1 =recursiveLPS(original,reverse.substring(0,reverse.length() -1));
46+
StringbestSubResult2 =recursiveLPS(original.substring(0,original.length() -1),reverse);
47+
if(bestSubResult1.length()>bestSubResult2.length()) {
48+
bestResult =bestSubResult1;
49+
}else {
50+
bestResult =bestSubResult2;
51+
}
52+
}
53+
}
54+
55+
returnbestResult;
56+
}
57+
}
Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
packagetest;
2+
3+
importstaticorg.junit.jupiter.api.Assertions.*;
4+
5+
importorg.junit.jupiter.api.Test;
6+
7+
classLongestPalindromicSubsequenceTests {
8+
9+
@Test
10+
voidtest1() {
11+
assertEquals(LongestPalindromicSubsequence.LPS(""),"");
12+
}
13+
14+
@Test
15+
voidtest2() {
16+
assertEquals(LongestPalindromicSubsequence.LPS("A"),"A");
17+
}
18+
19+
@Test
20+
voidtest3() {
21+
assertEquals(LongestPalindromicSubsequence.LPS("BABCBAB"),"BABCBAB");
22+
}
23+
24+
@Test
25+
voidtest4() {
26+
assertEquals(LongestPalindromicSubsequence.LPS("BBABCBCAB"),"BABCBAB");
27+
}
28+
29+
@Test
30+
voidtest5() {
31+
assertEquals(LongestPalindromicSubsequence.LPS("AAAAAAAAAAAAAAAAAAAAAAAA"),"AAAAAAAAAAAAAAAAAAAAAAAA");
32+
}
33+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp