-
Notifications
You must be signed in to change notification settings - Fork 2
/
CountPalindromicSubstrings.java
135 lines (110 loc) · 3.44 KB
/
CountPalindromicSubstrings.java
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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
package Leetcode;
/**
* @author kalpak
*
* Given a string, your task is to count how many palindromic substrings in this string.
*
* The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.
*
* Example 1:
*
* Input: "abc"
* Output: 3
* Explanation: Three palindromic strings: "a", "b", "c".
*
*
* Example 2:
*
* Input: "aaa"
* Output: 6
* Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
*
*
* Note:
*
* The input string length won't exceed 1000.
*
*/
public class CountPalindromicSubstrings {
// Brute Force
public static int countSubstringsNaive(String s) {
int count = 0;
if(s == null || s.length() == 0)
return count;
int length = s.length();
for(int i = 0; i < s.length(); i++) {
for(int j = i; j < s.length(); j++) {
String currentStr = s.substring(i, j + 1);
if(isPalindrome(currentStr))
count++;
}
}
return count;
}
private static boolean isPalindrome(String s) {
if(s.length() == 0 || s == null)
return false;
int left = 0;
int right = s.length() - 1;
while(left < right) {
if(s.charAt(left) != s.charAt(right))
return false;
left++;
right--;
}
return true;
}
public static int countSubstringsUsingExpandAroundCenter(String s) {
if(s == null || s.length() == 0)
return 0;
int length = s.length();
int count = 0;
for(int i = 0; i < s.length(); i++) {
count += countPalindromeAroundCenter(s, i, i); // Odd length palindrome. Single character at center
count += countPalindromeAroundCenter(s, i, i + 1); // Even length palindrome. Consecutive character at centre
}
return count;
}
private static int countPalindromeAroundCenter(String s, int left, int right) {
int result = 0;
while(left >= 0 && right < s.length()) {
if(s.charAt(left) != s.charAt(right))
break;
// Expand around center
left--;
right++;
result++;
}
return result;
}
public static int countSubstringsBottomsUp(String s) {
if(s.length() == 0 || s == null)
return 0;
int count = 0;
boolean[][] dp = new boolean[s.length()][s.length()];
// Base case: single letter substrings
for(int i = 0 ; i < s.length(); i++) {
dp[i][i] = true;
count++;
}
// Base case: double letter substrings
for(int i = 0 ; i < s.length() - 1; i++) {
dp[i][i + 1] = (s.charAt(i) == s.charAt(i+ 1));
count += (dp[i][i + 1]) ? 1 : 0;
}
for(int len = 3; len <= s.length(); len++) {
for(int i = 0, j = i + len - 1; j < s.length(); i++, j++) {
if(dp[i + 1][j - 1] && s.charAt(i) == s.charAt(j)) {
dp[i][j] = true;
count++;
}
}
}
return count;
}
public static void main(String[] args) {
System.out.println(countSubstringsNaive("abcba"));
System.out.println(countSubstringsUsingExpandAroundCenter("abcba"));
System.out.println(countSubstringsBottomsUp("abcba"));
}
}