680. Valid Palindrome II

leetcode easy

#csharp#easy#leetcode#string#tree#two-pointers

Task

Дана строка s, вернуть true, если s может быть палиндромом после удаления не более одного символа из нее.

Пример:

Input: s = "aba"

Output: true

C# solution

matched/original

public class Solution {
    private bool CheckPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public bool ValidPalindrome(string s) {
        int i = 0;
        int j = s.Length - 1;
        
        while (i < j) {
            if (s[i] != s[j]) {
                return CheckPalindrome(s, i, j - 1) || CheckPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private bool CheckPalindrome(string s, int i, int j) {
        while (i < j) {
            if (s[i] != s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public bool ValidPalindrome(string s) {
        int i = 0;
        int j = s.size() - 1;
        
        while (i < j) {
            if (s[i] != s[j]) {
                return CheckPalindrome(s, i, j - 1) || CheckPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}

Java solution

matched/original

class Solution {
    private boolean checkPalindrome(String s, int i, int j) {
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    public boolean validPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        
        while (i < j) {
            if (s.charAt(i) != s.charAt(j)) {
                return checkPalindrome(s, i, j - 1) || checkPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}

JavaScript solution

matched/original

class Solution {
    checkPalindrome(s, i, j) {
        while (i < j) {
            if (s[i] !== s[j]) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
    
    validPalindrome(s) {
        let i = 0;
        let j = s.length - 1;
        
        while (i < j) {
            if (s[i] !== s[j]) {
                return this.checkPalindrome(s, i, j - 1) || this.checkPalindrome(s, i + 1, j);
            }
            i++;
            j--;
        }
        
        return true;
    }
}

Python solution

matched/original

class Solution:
    def checkPalindrome(self, s: str, i: int, j: int) -> bool:
        while i < j:
            if s[i] != s[j]:
                return False
            i += 1
            j -= 1
        return True
    
    def validPalindrome(self, s: str) -> bool:
        i, j = 0, len(s) - 1
        
        while i < j:
            if s[i] != s[j]:
                return self.checkPalindrome(s, i, j - 1) or self.checkPalindrome(s, i + 1, j)
            i += 1
            j -= 1
        
        return True

Go solution

matched/original

package main

func checkPalindrome(s string, i, j int) bool {
    for i < j {
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
}

func validPalindrome(s string) bool {
    i, j := 0, len(s) - 1
    
    for i < j {
        if s[i] != s[j] {
            return checkPalindrome(s, i, j-1) || checkPalindrome(s, i+1, j)
        }
        i++
        j--
    }
    
    return true
}

Explanation

Algorithm

Создайте вспомогательную функцию checkPalindrome, которая принимает строку s и два указателя i и j. Эта функция возвращает логическое значение, указывающее, является ли подстрока s.substring(i, j) палиндромом.

Инициализируйте два указателя: i = 0 и j = s.length() - 1. Пока i < j, проверьте, совпадают ли символы в индексах i и j. Если нет, это значит, что нам нужно удалить один из этих символов.

Попробуйте оба варианта, используя checkPalindrome. Верните true, если либо checkPalindrome(s, i, j - 1), либо checkPalindrome(s, i + 1, j) возвращает true. Если мы выходим из цикла while, это значит, что исходная строка является палиндромом. Поскольку нам не нужно было использовать удаление, следует вернуть true.

😎