جائز پائيليروم ليٽ ڪوڊ حل


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Amazon ايپل Bloomberg ڪريو Microsoft جي Oracle رستو
اسٽرنگ ٻه اشارو

مسئلي جو بيان

ڏنو هڪ جملواسان کي اهو طئي ڪرڻو پوندو ته اهو هڪ پيلنڊروم آهي ، صرف الفاانمرڪڪ اکرن تي غور ڪندي يعني صرف نمبر ۽ الف. اسان کي الفابيٽ جي اکرن لاءِ ڪيسن کي به نظرانداز ڪرڻ گهرجي.

مثال

"A man, a plan, a canal: Panama"
true

وضاحت:

”اماناپلاناناڪنال پيناما“ هڪ صحيح پائيڊونوم آهي.

"race a car"
false

وضاحت:

”نسل راڻي“ پيالو نه آهي.

نائي نقطه نظر (ريورس سان موازنہ ڪرڻ)

اهو چيڪ ڪرڻ لاءِ ته ڇا هڪ تار تار آهي يا نه اسان صرف ان کي ريورس ڪري سگهون ٿا ۽ ان کي اصل تار سان تشبيح ڏيون ٿا. ان جي ور چٽڻ کانپوءِ جيڪڏهن اهو برابر ٿي وڃي ته پوءِ ڏنل تار هڪ سينڊروم آهي.
هن مسئلي ۾ اسان کي الفابيٽ ۽ انگن کانسواءِ سمورن اکرن کي نظرانداز ڪرڻ گهرجي. تنهنڪري ان لاءِ اسان ڏنل تار کي فلٽر ڪري سگھون ٿا ۽ سڀني ناپسنديده اکرن کي ڪ byڻ سان فلٽرنگ اسٽرنگ کي نئين متغير ۾ محفوظ ڪري سگھون ٿا. اچو ته هڪ مثال وٺون.

جائز پائيليروم ليٽ ڪوڊ حل

 

 

 

 

اسان ڏسي سگھون ٿا فلٽرنگ اسٽرنگ ۽ reversرندڙ فلٽرنگ اسٽرنگ برابر نه آھي ، انھيءَ ڪري اھو اھو صحيح پيلنروم نه آھي.

جائز پائيلنروم ليٽ ڪوڊ حل لاءِ عمل درآمد

سي ++ پروگرام

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
    string input;

    for(char c:s)
    {
        if(isAlphaNum(c))
            input+= lowerCase(c);
    }

    string reversed=input;
    reverse(reversed.begin(),reversed.end());

    if(input==reversed) return true;
    else return false;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

جاوا پروگرام

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       StringBuffer buf= new StringBuffer();
        
       for(char c: s.toCharArray())
       {
           if(isAlphaNum(c))
               buf.append(lowerCase(c));
       }
        
        String input,reversed;
        input= buf.toString();
        reversed= buf.reverse().toString();
        
        if(input.equals(reversed))
            return true;
        else 
            return false;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

صحيح پلنڊروم ليوٽ ڪوڊ حل لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي

اي (ن): ن ڏنل ڏني جي ڊيگهه آهي. اسان کي تار کي سڌو سنئون ڪرڻ گهرجي. ان ڪري وقت جي پيچيدگي O (n) هوندي.

خلائي پيچيدگي 

اي (ن): اسان کي فلٽرنگ تار ۽ ريورسنگ اسٽرنگ کي رکڻ لاءِ O (n) اضافي جڳهه جي ضرورت آهي.

بهتر ٿيل طريقه ڪار (ٻه اشارو استعمال ڪندي)

مٿين طريقي سان ، اسان ڏنل اسٽرنگ کي فلٽر ڪيو ۽ ان کي ذخيرو ڪرڻ لاءِ اضافي جاءِ استعمال ڪئي. اسان اهو جانچڻ لاءِ ٻه پوائنٽر پڻ استعمال ڪري سگهون ٿا ته اهو هڪ پيلنڊوم آهي يا نه ۽ اسان کي اضافي ميموري ٺاهڻ سان انهي کي فلٽر ڪرڻ يا محفوظ ڪرڻ جي ضرورت ناهي.

1. اسان ڇا ڪري سگهون ٿا ٻن پوائنٽرن جي متغيرات آهي ، شروع ۽ آخر ۽ انهن انٽ جي اسٽرنگ جي ٻن سرن سان اشارو ڪيو.
2. ھاڻي منتقل ڪر شروع پوائنٽر کي سا soي طرف ته اهو الفابيٽورڪ ڪردار ڏانهن اشارو ڪري ٿو. ساڳي طرح منتقل آخر کاٻي طرف وڃڻ ته اهو پڻ الف جي حساب واري اکر ڏانهن اشارو ڪري ٿو.
3. هاڻي چيڪ ڪريو ته ٻئيهي ڪردار ساڳيا آهن يا نه (ڪيسن کي نظرانداز ڪرڻ):

  • جيڪڏھن اھو برابر نه آھي ته پوءِ اسان knowاڻون ٿا ته اسٽرنگ ھڪ صحيح پلڊيروم نه آھي ، ان ڪري غلط موٽڻ.
  • ايلس ايندڙ آثارن ڏانهن جاري آهي ۽ ٻنهي اشارن کي حرڪت ڪرڻ جو ساڳيو عمل ٻيهر ورتائين شروعات.

4. لوپ ختم ٿيڻ کان پوءِ ، تار کي چيو ويندو آهي پيلڊروم ، تنهن ڪري موٽي سچ ٿيو.

جائز پائيلنروم ليٽ ڪوڊ حل لاءِ عمل درآمد

سي ++ پروگرام

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

bool isAlphaNum(char c)
{
    if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
        return true;
    return false;
}
    
char lowerCase(char c)
{
    if(65<=c && c<=90)
        return c+32;
    else 
        return c;
}
    
bool isPalindrome(string s) 
{
        int start=0,end=s.size()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s[start])) start++;
            while(start<end && !isAlphaNum(s[end])) end--;
           
            if(lowerCase(s[start])!=lowerCase(s[end]))  return false; 
            
            start++;
            end--;
        }
        
        return true;

}

int main() 
{
    string s="A man, a plan, a canal: Panama";
    if(isPalindrome(s))
        cout<<"true"<<endl;
    else
        cout<<"false"<<endl;

  return 0; 
}
true

جاوا پروگرام

import java.lang.*;

class Rextester
{  
    static boolean isAlphaNum(char c)
    {
        if( (48<=c && c<=57) || (65<=c && c<=90) || (97<=c && c<=122)) 
            return true;
        else
            return false;
    }
    
    static char lowerCase(char c)
    {
        if(65<=c && c<=90)
            return (char)(c+32);
        else 
            return c;
    }
    
    public static boolean isPalindrome(String s) 
    {
       int start=0,end=s.length()-1;
        
        while(start<end)
        {
            while(start<end && !isAlphaNum(s.charAt(start))) start++;
            while(start<end && !isAlphaNum(s.charAt(end))) end--;
           
            if(lowerCase(s.charAt(start))!=lowerCase(s.charAt(end)))  
                return false; 
            
            start++;
            end--;
        }
        
        return true;
        
    }
    
    public static void main(String args[])
    {
       String s="A man, a plan, a canal: Panama";
       System.out.println(isPalindrome(s));   
    }
}
true

صحيح پلنڊروم ليوٽ ڪوڊ حل لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي

اي (ن): اسان فقط هڪ ڀيرو تار جو ڪردار ڏسي رهيا آهيون. ان ڪري وقت جي پيچيدگي O (n) آهي.

خلائي پيچيدگي 

اي (1): اسان کي هتي وڌيڪ اضافي يادگيري جي ضرورت ناهي.