هڪ اسٽرنگ ليٽ ڪوڊ جو حل


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

مسئلي جو بيان

انهي مسئلي ۾ هڪ جملو ڏنو ويو آهي ۽ اسان کي هن تار جي اڳئين آواز کي واپس ڪرڻو پوندو.

مثال

"hello"
"holle"

وضاحت:
رد ڪرڻ کان پهرين: “ايڇello"
رد ڪرڻ بعد: “ايڇolle"

"leetcode"
"leotcede"

وضاحت:
هڪ اسٽرنگ ليٽ ڪوڊ جو حل

پهچ 1 (استعمال ڪندي چتي)

اسان کي انپٽ سٽرنگ ۾ موجود واويلا کي موٽائيڻو پوندو. تنهن ڪري اسان سمورو ترتيب ۾ سمورو وايون کو کاٻي کان سا rightي ترتيب ۾ رکي سگهون ٿا. وري ٻيهر اسين تار ڳولي سگھون ٿا ۽ هر ويڪر واري ڪردار کان کاٻي کان سا rightي طرف وڃي اسين ان کي اسٽيڪ جي مٿين قيمت سان مٽائي ڇڏينداسين.

الورورٿم

  • سڀني حرفن جي اکرن کي هڪ سيٽ ۾ محفوظ ڪريو.
  • اسٽيڪ ٺاهيو ۽ دٻايو سڀني واڪيل اکرن کي انٽ سٽرنگ ۾ موجود کان کاٻي کان سا rightي طرف.
  • ھاڻي وري ھر ھڪ ڪردار لاءِ تار گھرايو. جيڪڏهن موجوده ڪردار واويلا آهي ، ان کي اسٽيڪ جي چوٽي چڪر (انٽ اسٽرنگ جي دائیں ويلو ڪردار) سان ان کي مٽايو ۽ ان کي اسٽيڪ مان هٽايو.
  • تبديل ٿيل جملو واپس ڪريو.

هڪ اسٽرنگ ليٽ ڪوڊ حل جي ريورس واويل تي عمل درآمد

سي ++ پروگرام

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};
    stack<char> stack;
    for(char c:s)
    {
        if(vowels.count(c)) stack.push(c);
    }

    for(char& c:s)
    {
        if(vowels.count(c)) 
        {
            c=stack.top();
            stack.pop();
        }
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

جاوا پروگرام

import java.util.*;

class Rextester
{ 
    public static String reverseVowels(String s) {

        char[] arr= s.toCharArray();

        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');

        Stack<Character> stack=new Stack<Character>();

        for(char c:arr)
        {
            if(vowels.contains(c)) stack.push(c);
        }

        for(int i=0;i<arr.length;i++)
        {
            if(vowels.contains(arr[i])) 
            {
                arr[i]=stack.pop();
            }
        }

        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

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

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

اي (اين): اسان صرف ٻه ڀيرا اسٽرنگ کي پار ڪيو. اسٽيڪ تي پُش ۽ پاپ آپريشن پڻ مسلسل وقت وٺندو آهي ۽ ويڪر جي سيٽ ۾ صرف 10 عنصر هوندا آهن (يعني اهو ڪردار ڳولهڻ لاءِ مسلسل وقت وٺندو) ، تنهن ڪري وقت جي پيچيدگي O (N) آهي.

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

اي (اين): بدترين اسٽيڪ ۾ انپٽ سٽرنگ جا سڀ ڪردار ٿي سگھن ٿا. ان ڪري خلائي پيچيدگي اي (اين) آهي.

پهچ 2 (سنگل پاس ٻه اشارو استعمال ڪندي)

اسان هيٺ ڏنل الگورتھم سان ٻن پوائنٽرن کي استعمال ڪندي ھڪڙي ويجھڙائي ۾ حلوت کي رد ڪري سگھون ٿا.

  • ٻه متغير ٺاهيو شروع ۽ آخر کاٻي ۽ سا respectivelyي طرف کان ويڪر ڏانهن اشارو ڪرڻ لاءِ.
  • شروعاتي طور تي شروع= 0 ۽ آخر= ڊيگهه (اسٽرنگ) -1.
  • ھاڻي لوپ کي هلائڻ دوران شروعات.
  • هن لوپ جي اندر اندر اهي ٻه movingرڻ وارا هلندا آهن انهن ڏي pointرن کي شروعات ۽ آخر کان کاٻي کان سا rightي ۽ کاٻي کان بالترتیب اڳتي وڌائين ٿا ته اهي ايندڙ واوا ڏانهن اشارو ڪن
  • شروعات ۽ آخر سان ظاهر ڪيل ٻن ويڪر اکرن کي مٽايو.
  • واڌارو شروع ۽ گھٽجي ٿو آخر 1 جي.
  • واپس اچو نئين تار کي جڏهن شروع وڏو ٿي ٿو آخر

هڪ اسٽرنگ ليٽ ڪوڊ حل جي ريورس واويل تي عمل درآمد

سي ++ پروگرام

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

string reverseVowels(string s) {

    set<char> vowels={'a','e','i','o','u','A','E','I','O','U'};

    int start=0,end=s.length()-1;
    while(start<end)
    {
        while(start<end && !vowels.count(s[start])) start++;

        while(start<end && !vowels.count(s[end])) end--;

        char temp=s[start];
        s[start]=s[end];
        s[end]=temp;

        start++;
        end--;
    }

    return s;
}

int main() 
{
    string s="leetcode";
    cout<< reverseVowels(s)<<endl;
   
   return 0; 
}
leotcede

جاوا پروگرام

import java.util.*;

class Rextester
{ 
    public static String reverseVowels(String s) {

       char[] arr= s.toCharArray();
        
        Set<Character> vowels=new HashSet<Character>();
        vowels.add('a');
        vowels.add('e');
        vowels.add('i');
        vowels.add('o');
        vowels.add('u');
        vowels.add('A');
        vowels.add('E');
        vowels.add('I');
        vowels.add('O');
        vowels.add('U');
        
       int start=0,end=arr.length-1;
        while(start<end)
        {
            while(start<end && !vowels.contains(arr[start])) start++;
            
            while(start<end && !vowels.contains(arr[end])) end--;
            
            char temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            
            start++;
            end--;
        }
        
        return new String(arr);
    }
    
    public static void main(String args[])
    {
        String s="leetcode";
        System.out.println(reverseVowels(s));
        
    }
}
leotcede

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

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

اي (اين): اسٽرنگ جو هر ڪردار صرف هڪ ڀيرو گهمڻ آهي ، تنهن ڪري وقت جي پيچيدگي O (N) آهي.

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

اي (1): vowels جو سيٽ نه آهي صرف اضافي جڳهه استعمال ڪئي ويندي آهي جنهن ۾ صرف 10 عنصر هجن (يعني مستقل جاءِ). ان ڪري خلائي پيچيدگي اي آهي (1).