FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DynamicProgramming/LongestPalindromicSubsequence.java at master · dsfb/Java · GitHub
dsfb
/
Java
Public
forked from
TheAlgorithms/Java
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DynamicProgramming
/
LongestPalindromicSubsequence.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
62 lines (51 loc) · 2.03 KB
Breadcrumbs
Java
/
DynamicProgramming
/
LongestPalindromicSubsequence.java
Copy path
File metadata and controls
62 lines (51 loc) · 2.03 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
package
test
;
import
java
.
io
.*;
import
java
.
util
.*;
/**
* Algorithm explanation https://www.educative.io/edpresso/longest-palindromic-subsequence-algorithm
*/
public
class
LongestPalindromicSubsequence
{
public
static
void
main
(
String
[]
args
) {
String
a
=
"BBABCBCAB"
;
String
b
=
"BABCBAB"
;
String
aLPS
=
LPS
(
a
);
String
bLPS
=
LPS
(
b
);
System
.
out
.
println
(
a
+
" => "
+
aLPS
);
System
.
out
.
println
(
b
+
" => "
+
bLPS
);
}
public
static
String
LPS
(
String
original
)
throws
IllegalArgumentException
{
StringBuilder
reverse
=
new
StringBuilder
(
original
);
reverse
=
reverse
.
reverse
();
return
recursiveLPS
(
original
,
reverse
.
toString
());
}
private
static
String
recursiveLPS
(
String
original
,
String
reverse
) {
String
bestResult
=
""
;
// no more chars, then return empty
if
(
original
.
length
() ==
0
||
reverse
.
length
() ==
0
) {
bestResult
=
""
;
}
else
{
// if the last chars match, then remove it from both strings and recur
if
(
original
.
charAt
(
original
.
length
() -
1
) ==
reverse
.
charAt
(
reverse
.
length
() -
1
)) {
String
bestSubResult
=
recursiveLPS
(
original
.
substring
(
0
,
original
.
length
() -
1
),
reverse
.
substring
(
0
,
reverse
.
length
() -
1
));
bestResult
=
reverse
.
charAt
(
reverse
.
length
() -
1
) +
bestSubResult
;
}
else
{
// otherwise (1) ignore the last character of reverse, and recur on original and updated
// reverse again
// (2) ignore the last character of original and recur on the updated original and reverse
// again
// then select the best result from these two subproblems.
String
bestSubResult1
=
recursiveLPS
(
original
,
reverse
.
substring
(
0
,
reverse
.
length
() -
1
));
String
bestSubResult2
=
recursiveLPS
(
original
.
substring
(
0
,
original
.
length
() -
1
),
reverse
);
if
(
bestSubResult1
.
length
() >
bestSubResult2
.
length
()) {
bestResult
=
bestSubResult1
;
}
else
{
bestResult
=
bestSubResult2
;
}
}
}
return
bestResult
;
}
}
Back
|
FazBrowse Home
|
New Git URL