Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/680.html
680. Valid Palindrome II (Easy)
Given a non-empty string s
, you may delete at most one character. Judge whether you can make it a palindrome.
Example 1:
Input: "aba" Output: True
Example 2:
Input: "abca" Output: True Explanation: You could delete the character 'c'.
Note:
- The string will only contain lowercase characters a-z. The maximum length of the string is 50000.
Companies:
Facebook, Google, Yahoo
Related Topics:
String
Similar Questions:
Solution 1.
-
class Solution { public boolean validPalindrome(String s) { int low = 0, high = s.length() - 1; while (low < high) { char c1 = s.charAt(low), c2 = s.charAt(high); if (c1 == c2) { low++; high--; } else { boolean flag1 = true, flag2 = true; for (int i = low, j = high - 1; i < j; i++, j--) { char c3 = s.charAt(i), c4 = s.charAt(j); if (c3 != c4) { flag1 = false; break; } } for (int i = low + 1, j = high; i < j; i++, j--) { char c3 = s.charAt(i), c4 = s.charAt(j); if (c3 != c4) { flag2 = false; break; } } return flag1 || flag2; } } return true; } } ############ class Solution { public boolean validPalindrome(String s) { for (int i = 0, j = s.length() - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return check(s, i + 1, j) || check(s, i, j - 1); } } return true; } private boolean check(String s, int i, int j) { for (; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; } }
-
// OJ: https://leetcode.com/problems/valid-palindrome-ii/ // Time: O(N) // Space: O(1) class Solution { public: bool validPalindrome(string s) { int i = 0, j = s.size() - 1; while (i < j && s[i] == s[j]) ++i, --j; if (i >= j) return true; auto valid = [&](int i, int j) { while (i < j && s[i] == s[j]) ++i, --j; return i >= j; }; return valid(i + 1, j) || valid(i, j - 1); } };
-
class Solution: def validPalindrome(self, s: str) -> bool: def check(i, j): while i < j: if s[i] != s[j]: return False i, j = i + 1, j - 1 return True i, j = 0, len(s) - 1 while i < j: if s[i] != s[j]: return check(i, j - 1) or check(i + 1, j) i, j = i + 1, j - 1 return True ############ class Solution(object): def validPalindrome(self, s): """ :type s: str :rtype: bool """ isPalindrome = lambda s: s == s[::-1] strPart = lambda s, x: s[:x] + s[x + 1:] left = 0 right = len(s) - 1 while left < right: if s[left] != s[right]: return isPalindrome(strPart(s, left)) or isPalindrome(strPart(s, right)) left += 1 right -= 1 return True
-
func validPalindrome(s string) bool { check := func(i, j int) bool { for ; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return false } } return true } for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 { if s[i] != s[j] { return check(i+1, j) || check(i, j-1) } } return true }
-
function validPalindrome(s: string): boolean { for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return ( isPalinddrome(s.slice(i, j)) || isPalinddrome(s.slice(i + 1, j + 1)) ); } } return true; } function isPalinddrome(s: string): boolean { for (let i: number = 0, j = s.length - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; }
-
/** * @param {string} s * @return {boolean} */ var validPalindrome = function (s) { let check = function (i, j) { for (; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return false; } } return true; }; for (let i = 0, j = s.length - 1; i < j; ++i, --j) { if (s.charAt(i) != s.charAt(j)) { return check(i + 1, j) || check(i, j - 1); } } return true; };