Difficulty:easy
More:[目录] LeetCode Java 实现 https://www.cnblogs.com/yongh/p/9977350.html
- Description
- https://leetcode.com/problems/valid-palindrome-ii/
- Given an array of integers, return indices of the two numbers such that they add up to a specific
- 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'.
- Intuition
1.Make use of two pointers.
- 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 isPalindrome(s, i, j-1) || isPalindrome(s, i+1, j);
- }
- return true;
- }
- private boolean isPalindrome(String s, int i, int j){
- while(i < j){
- if(s.charAt(i++) != s.charAt(j--))
- return false;
- }
- return true;
- }
- Complexity
- Time complexity : O(n)
- Space complexity : O(1)
- What I've learned
- 1. It's important to learn and make use of the method isPalindrome()
More:[目录] LeetCode Java 实现 https://www.cnblogs.com/yongh/p/9977350.html
来源: http://www.bubuko.com/infodetail-3219206.html