バックル練習日記——返信文字列を検証するⅡ

目次

題:検証回文文字列II

暴力解読

貪欲アルゴリズム

タイトル:検証回文文字列Ⅱ
空でない文字列sを指定し、最大1文字を削除します.返信文字列にできるかどうかを判断します.
例1:
入力:aba出力:True例2:
入力:abca出力:True解釈:c文字を削除できます.注意:
文字列にはa-zからの小文字のみが含まれます.文字列の最大長は50000です.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/valid-palindrome-ii著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
暴力解読
最も素朴な方法を考える:まず元の列が回文列であるかどうかを判断し、もしそうであればtrueに戻る.そうでない場合は、削除された位置として各位置を列挙し、残りの文字列がエコー列であるか否かを判断する.このアプローチの漸進的時間複雑度はO(n^2)であり,解題が時間制限を超える.
欲張りアルゴリズム
いつものように、まずコードをつけます.

public class ValidPalindrome {
    public static boolean validPalindrome(String s) {
        int low = 0;
        int high = s.length() - 1;
        while (low < high){
            char c1 = s.charAt(low);
            char c2 = s.charAt(high);
            if (c1 == c2){
                low ++;
                high --;
            }else{
                boolean flag1 = true;
                boolean flag2 = true;
                for (int i = low + 1, j = high; i < j; i++, j--) {
                    char c3 = s.charAt(i);
                    char c4 = s.charAt(j);
                    if (c3 != c4){
                        flag1 = false;
                        break;
                    }
                }
                for (int i = low, j = high - 1; i < j; i++, j--) {
                    char c3 = s.charAt(i);
                    char c4 = s.charAt(j);
                    if (c3 != c4){
                        flag2 = false;
                        break;
                    }
                }
                return flag1 || flag2;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(validPalindrome("abca"));
    }
}

一般に、返信文字列を解決する方法は、文字列の先頭と末尾をそれぞれ指す2つのポインタであり、2つのポインタが中間に寄せられ、ポインタが指す値が同じ文字列が返信文字列である.
しかし、この問題では、文字列の1つを削除できる拡張子が与えられています.
同様に、2つのポインタが指す値が異なる場合、2つの処理状況に分けることができます.1つ目はヘッドポインタの値を削除し、2つ目はテールポインタの値を削除し、2つの場合、いずれかが返信文字列を満たす場合、問題の要求に合致します.