有効な回文


難易度 簡単に
よく聞かれる インフォシス MAQ ノキア o9ソリューション
文字列 XNUMXつのポインター

与えられた 文字列 長さnのs。 文字列が有効な回文であるかどうかを確認するプログラムを作成します。 そうでない場合は、文字列から最大XNUMX文字を削除して、回文にすることができます。

逆と同じ文字列は、回文として知られています。

例:

  1. 文字列=「ニティーン」と逆文字列=「ニティーン」は同じであるため、回文です。
  2. string =“ apple”とreverse string =“ elppa”は同じではないため、回文ではありません。

有効な回文

入力: s =“ abcdba”

出力: はい(「c」または「d」のいずれかを削除することにより)

入力: s =“ abba”

出力: はい(すでに回文)

入力: s =“ blue”

出力: いいえ

有効な回文のアルゴリズム

これで、問題の説明を最も簡単な方法で理解できました。 したがって、実装部分では、実装に使用されるアルゴリズムに移動します。

  1. 文字列を初期化します。
  2. 開始インデックスと終了インデックスポインタを使用してトラバースを開始します。
  3. 両方のインデックスの文字が等しいインクリメント開始ポインタとデクリメント終了ポインタであるかどうかを確認します。 開始インデックスが終了インデックス以上の場合、trueを返します。
  4. それ以外の場合は、これらの文字のXNUMXつを削除して回文を作成してみてください。
  5. インデックスの開始時に文字を削除すると、回文がtrueを返します。
  6. それ以外の場合、インデックスの終了時に文字を削除すると、回文がtrueを返します。
  7. それ以外の場合はfalseを返します。

有効な回文をチェックするC ++プログラム

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

bool isPalindrome(string::iterator low, string::iterator high){ 
    while(low < high){ 
       if(*low != *high) 
          return false; 
       low++; 
       high--; 
    } 
    return true; 
} 
  
bool Palindrome(string s){ 
    int low = 0, high = s.length() - 1; 
  
    while(low < high){ 
        if(s[low] == s[high]){ 
            low++; 
            high--; 
        } 
        else{ 
            if(isPalindrome(s.begin() + low + 1, s.begin() + high)) 
                return true; 
  
            if (isPalindrome(s.begin() + low, s.begin() + high - 1)) 
                return true; 
  
            return false; 
        } 
    } 
  
    return true; 
} 
  
int main(){ 
    string s = "abcdba"; 
    
    if(Palindrome(s)){
        cout<<"Yes";
    } 
    else{
        cout<<"No";
    }
    return 0; 
}
Yes

有効な回文をチェックするJavaプログラム

import java.util.*; 
  
class validPalindrome{ 
  
    static boolean isPalindrome(String s, int low, int high){ 
        while(low < high){ 
            if(s.charAt(low) != s.charAt(high)) 
                return false; 
            low++; 
            high--; 
        } 
        return true; 
    } 
  
    static boolean Palindrome(String s){ 
  
        int low = 0, high = s.length() - 1; 
  
        while(low < high){ 
  
            if(s.charAt(low) == s.charAt(high)){ 
                low++; 
                high--; 
            }  
            else{ 
  
                if(isPalindrome(s, low + 1, high)) 
                    return true; 
  
                if(isPalindrome(s, low, high - 1)) 
                    return true; 
                return false; 
            } 
        } 
  
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abcdba"; 
        
        if(Palindrome(s)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    } 
} 
Yes

複雑さの分析

時間の複雑さ

O(N)  ここで、nは指定された文字列の長さです。

補助スペース

O(1) ここでは余分なスペースを使用しないためです。

リフレッシュ