---
# System prepended metadata

title: 680. Valid Palindrome II
tags: [LeetCode]

---

---
tags: LeetCode
---

# 680. Valid Palindrome II
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.

輸入範本如下
```C#
public class Solution {
    public bool ValidPalindrome(string s) {
        
    }
}
```



### 直覺想法
判斷這是不是一個迴文 , 但是允許忽略一個字.    
因為不知道應該忽略左邊還是右邊的字 , 所以在判斷迴文時 , 若遇到不同的字時 , 需要兩個都做一遍 (忽略左邊的字 , 去看剩下的字是否迴文 , 以及忽略右邊的字去看剩下的字是否迴文)
1. 遞迴解
    - 需要將已經忽略字的情報傳下去.
    - 判斷剩下的字是否為迴文
```C#
88 ms	42.9 MB
You are here!
Your runtime beats 93.51 % of csharp submissions
public bool ValidPalindrome(string s)
{
    return IsPalindrome(s, false);

    bool IsPalindrome(string str, bool hasIgnore)
    {
        for (int l = 0, r = str.Length - 1; l < r; l++, r--)
        {
            if (str[l] != str[r])
            {
                if (hasIgnore) return false;
                return IsPalindrome(str.Substring(l + 1, r - (l + 1) + 1), true) || 
                       IsPalindrome(str.Substring(l, (r - 1) - l + 1), true);
            }
        }
        return true;
    }
}
```

2. 迴圈解
    - 遇到不同字時 , 分別判斷忽略左右字後的結果是否為迴文
```C#
88 ms	42.7 MB
You are here!
Your runtime beats 93.51 % of csharp submissions.
public bool ValidPalindrome(string s)
{
    for (int l = 0, r = s.Length - 1; l < r; l++, r--)
    {
        if (s[l] != s[r])
        {
            return IsPalindrome(s.Substring(l + 1, r - (l + 1) + 1)) || 
                   IsPalindrome(s.Substring(l, (r - 1) - l + 1));
        }
    }
    return true;

    bool IsPalindrome(string str)
    {
        for (int l = 0, r = str.Length - 1; l < r; l++, r--)
        {
            if (str[l] != str[r])
            {
                return false;
            }
        }
        return true;
    }
}
```








### Thank you! 

You can find me on

- [GitHub](https://github.com/s0920832252)
- [Facebook](https://www.facebook.com/fourtune.chen)

若有謬誤 , 煩請告知 , 新手發帖請多包涵

# :100: :muscle: :tada: :sheep: 
