درست Palindrome  


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے انفوسس میک نوکیا o9 حل
سلک دو پوائنٹر

دیا ہوا a سٹرنگ s کی لمبائی n. ایک پروگرام لکھیں تاکہ معلوم ہو سکے کہ سٹرنگ درست پیلنڈروم ہے یا نہیں۔ اگر نہیں تو آپ اس کو پالینڈوم بنانے کے لind زیادہ سے زیادہ ایک حرف کو تار سے حذف کرسکتے ہیں۔

کوئی بھی سٹرنگ جو اس کے ریورس کے مترادف ہے اسے پیلینڈوم کہا جاتا ہے۔

مثال کے طور پر:

  1. سٹرنگ = “نائنن” اور ریورس سٹرنگ = “نائنن” جو ایک جیسی ہیں لہذا یہ ایک پالینڈوم ہے۔
  2. سٹرنگ = "ایپل" اور ریورس سٹرنگ = "ایلپا" جو ایک جیسی نہیں ہیں لہذا یہ پالینڈوم نہیں ہے۔

درست Palindromeپن

مثال کے طور پر  

ان پٹ: s = "abcdba"

: پیداوار ہاں (یا تو 'c' یا 'd' کو ہٹا کر)

ان پٹ: s = "عبا"

: پیداوار ہاں (پہلے ہی ایک پلینڈوم)

ان پٹ: s = "نیلے"

: پیداوار نہیں

درست Palindrome کے لئے الگورتھم  

اب ہم مسئلے کے بیان کو آسان طریقے سے سمجھتے ہیں۔ لہذا ، اب نفاذ کے حص forے کے ل implementation عمل درآمد کے ل for استعمال شدہ الگورتھم میں منتقل ہوجائیں۔

  1. ایک تار شروع کریں۔
  2. شروعاتی اشاریہ کا اختتام کرکے اور انڈیکس پوائنٹر کو ختم کرنا شروع کریں۔
  3. جانچ پڑتال کریں کہ کیا دونوں اشاریہ جات میں کردار برابر بڑھتی ہوئی پوائنٹر اور کمی ختم ہونے والا پوائنٹر ہے۔ اگر آغاز انڈیکس ختم ہونے والے انڈیکس سے زیادہ یا اس کے برابر ہے تو صحیح ہے۔
  4. ورنہ ان میں سے کسی ایک حرف کو ختم کرکے پالینڈوم بنانے کی کوشش کریں۔
  5. اگر شروعاتی اشاریہ میں کردار کو ہٹانے سے پیلینڈوم میں نتیجہ برآمد ہوتا ہے تو یہ سچ ہے۔
  6. بصورت دیگر اگر پیل انڈوم کے اختتام پذیر کے اختتام پر کردار کو ہٹانا صحیح ہوجائے گا۔
  7. ورنہ جھوٹی واپسی۔

C ++ پروگرام درست Palindrome چیک کرنے کے لئے  

#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

جائز Palindrome چیک کرنے کے لئے جاوا پروگرام  

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

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

اے (ن)  جہاں n دیئے گئے تار کی لمبائی ہے۔

یہ بھی دیکھتے ہیں
ہیڈ پوائنٹر کے بغیر منسلک فہرست سے نوڈ کو حذف کریں

معاون جگہ

O (1) کیونکہ ہم یہاں کوئی اضافی جگہ استعمال نہیں کرتے ہیں۔

ریفرنس