واکه های معکوس یک حلقه کد رشته ای


سطح دشواری ساده
اغلب در آمازون فیس بوک گوگل
رشته دو نشانگر

بیان مسأله

در این مشکل a رشته داده شده است و ما فقط باید واکه های این رشته را برعکس کنیم.

مثال

"hello"
"holle"

شرح:
قبل از برگشت: "ساعتello"
پس از برگشت: "ساعتolle"

"leetcode"
"leotcede"

شرح:
واکه های معکوس یک حلقه کد رشته ای

رویکرد 1 (با استفاده از پشته)

فقط باید واکه های موجود در رشته ورودی را معکوس کنیم. بنابراین می توانیم تمام واکه ها را به همان ترتیب از چپ به راست در یک پشته ذخیره کنیم. سپس دوباره می توانیم رشته را رد کنیم و برای هر حرف واکه از چپ به راست آن را با بالاترین مقدار پشته جایگزین خواهیم کرد.

الگوریتم

  • تمام حروف صدادار را در یک مجموعه ذخیره کنید.
  • یک پشته ایجاد کنید و تمام نویسه های مصوت موجود در رشته ورودی را از چپ به راست فشار دهید.
  • اکنون دوباره رشته را برای هر کاراکتر رد کنید. اگر نویسه فعلی مصوت است ، آن را با بالاترین کاراکتر پشته جایگزین کنید (صحیح ترین صوت مصوتی صوتی ورودی) و آن را از پشته خارج کنید.
  • رشته تبدیل شده را برگردانید.

پیاده سازی برای واکه های معکوس یک راه حل کد کد

برنامه C ++

#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) است.

پیچیدگی فضا 

بر): در بدترین حالت پشته می تواند تمام نویسه های رشته ورودی را داشته باشد. از این رو پیچیدگی فضا O (N) است.

رویکرد 2 (تک پاس با استفاده از دو نشانگر)

ما همچنین می توانیم با استفاده از دو نشانگر با استفاده از الگوریتم زیر ، واکه ها را معکوس کنیم:

  • دو متغیر ایجاد کنید شروع و پایان برای اشاره به حروف صدادار به ترتیب از چپ و راست
  • مقدماتی به عنوان شروع= 0 و پایان= طول (رشته) -1.
  • در حالی که حلقه را اجرا کنید شروع کنید.
  • در داخل این حلقه دو حلقه برای حرکت این دو نشانگر از چپ به راست و راست به چپ به ترتیب شروع و پایان می یابند به طوری که آنها به مصوت بعدی اشاره می کنند.
  • دو کاراکتر مصوت را که با شروع و پایان مشخص شده اند عوض کنید.
  • افزایش شروع و کاهش می یابد پایان توسط 1.
  • رشته جدید را وقتی برگردانید شروع بزرگتر می شود پایان

پیاده سازی برای واکه های معکوس یک راه حل کد کد

برنامه C ++

#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) است.

پیچیدگی فضا 

O (1): از فضای اضافی بجز مجموعه واکه هایی که فقط 10 عنصر دارند (یعنی فضای ثابت) استفاده نمی شود. از این رو پیچیدگی فضا O است (1).