Problem: 647. Palindromic Substrings
Approaches
-
Simplest approach will be checking all possible combinations of the substrings and check which one is palindromic
O(n ^ 2) with each string to be around n / 2
=> O(n ^ 3) => more than 10 ^ 9
and working with string is not so good Can we apply DP here to keep track of the palindrom that is already checked
dp[][]
dp[i][j] will be either 0, 1, or 2
with 0 is unknown
with 1 is false
and 2 is true
dp[i][j] = 1 means that is not palindromic
dp[i][j] = 2 means palindromic checked
if the string has length 1 => true for sure
else:
check dp first
check the first and last string then check recurse(left + 1, right - 1);
This will require to start with each substring starting with a specific index and check the length of it
At most, a substring can have a length of n
check from length 1 to length n
with that,
with length l, check from index 0 till index i as long as i + l < n; i++
Solution
class Solution {
int[][] dp;
String string;
public int recurse(int start, int end) {
if (dp[start][end] != 0) {
return dp[start][end];
} else {
int isPalindromic = 0;
if (start == end) {
isPalindromic = 2;
} else if (string.charAt(start) != string.charAt(end)) {
isPalindromic = 1;
} else { // char at start and end are equal
if (start + 1 == end) {
isPalindromic = 2;
} else {
isPalindromic = recurse(start + 1, end - 1);
}
}
dp[start][end] = isPalindromic;
return dp[start][end];
}
}
public int countSubstrings(String s) {
string = s;
dp = new int[string.length()][string.length()];
for (int r = 0; r < dp.length; r ++) {
for (int c = 0; c < dp.length; c++) {
dp[r][c] = 0; // fill with unknown
}
}
for (int length = 1; length <= s.length(); length ++) {
for (int idx = 0; idx + length - 1 < s.length(); idx ++) {
// StringBuilder sb = new StringBuilder();
// for (int i = idx; i < idx + length; i++) {
// sb.append(s.charAt(i));
// }
// System.out.println(sb.toString());
recurse(idx, idx + length - 1);
}
}
int result = 0;
for (int r = 0; r < dp.length; r ++) {
for (int c = 0; c < dp.length; c++) {
if (dp[r][c] == 2) result ++;
}
}
return result;
}
}
Top comments (0)