publicstaticbooleanvalidPalindrome_bf(String s){ int len = s.length(); if (len <= 2 || validPalindrome(s, 0, len - 1)) { returntrue; }
for (int i = 0; i < len; i++) { String str = s.substring(0, i) + s.substring(i + 1, len); if (validPalindrome(str, 0, str.length() - 1)) { returntrue; } }
returnfalse; }
publicstaticbooleanvalidPalindrome(String s, int left, int right){ int len = s.length(); if (left >= len || right < 0 || left > right) { returnfalse; }
while (left < right) { if (s.charAt(left) != s.charAt(right)) { returnfalse; } left++; right--; }
returntrue; }
Analysis
Time Complexity: O(n2)
Space Complexity: O(1)
Recursion
Recursion solution is also easy, it is silimar to the two pointers approach.
// Two Pointers time: O(n) space: O(1) publicstaticbooleanvalidPalindrome_tp(String s){ int len = s.length(); if (len <= 2) { returntrue; }
int left = 0; int right = len - 1; while (left < right) { if (s.charAt(left) != s.charAt(right)) { return validPalindrome(s, left + 1, right) || validPalindrome(s, left, right - 1); } else { left++; right--; } }
returntrue; }
publicstaticbooleanvalidPalindrome(String s, int left, int right){ int len = s.length(); if (left >= len || right < 0 || left > right) { returnfalse; }
while (left < right) { if (s.charAt(left) != s.charAt(right)) { returnfalse; } left++; right--; }
returntrue; }
Analysis
Time Complexity: O(n).
Space Complexity: O(1).
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)