---
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.

輸入範本如下

public class Solution {
    public bool ValidPalindrome(string s) {
        
    }
}

### 直覺想法
判斷這是不是一個迴文 , 但是允許忽略一個字.
因為不知道應該忽略左邊還是右邊的字 , 所以在判斷迴文時 , 若遇到不同的字時 , 需要兩個都做一遍 (忽略左邊的字 , 去看剩下的字是否迴文 , 以及忽略右邊的字去看剩下的字是否迴文)
1. 遞迴解
- 需要將已經忽略字的情報傳下去.
- 判斷剩下的字是否為迴文

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. 迴圈解
- 遇到不同字時 , 分別判斷忽略左右字後的結果是否為迴文

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: