ស្រៈបញ្ច្រាសនៃដំណោះស្រាយខ្សែអក្សរឡេឡេលេខកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ ក្រុមហ៊ុន Amazon Facebook ក្រុមហ៊ុន google
ខ្សែអក្សរ ចំណុចពីរ

សេចក្តីថ្លែងការណ៍បញ្ហា។

ក្នុងបញ្ហានេះក ខ្សែអក្សរ ត្រូវបានផ្តល់ឱ្យហើយយើងត្រូវតែបញ្ច្រាសតែស្រៈនៃខ្សែអក្សរនេះ។

ឧទាហរណ៍

"hello"
"holle"

ការពន្យល់:
មុនពេលត្រឡប់ក្រោយ៖“ ជello"
បន្ទាប់ពីបញ្ច្រាស៖“ ជolle"

"leetcode"
"leotcede"

ការពន្យល់:
ស្រៈបញ្ច្រាសនៃដំណោះស្រាយខ្សែអក្សរឡេឡេលេខកូដ

វិធីសាស្រ្ត ១ (ការប្រើប្រាស់ ជង់)

យើងគ្រាន់តែត្រូវបញ្ច្រាសស្រៈដែលមាននៅក្នុងខ្សែបញ្ចូល។ ដូច្នេះយើងអាចទុកស្រៈទាំងអស់នៅក្នុងជង់ក្នុងលំដាប់ដូចគ្នាពីឆ្វេងទៅស្តាំ។ បន្ទាប់មកម្តងទៀតយើងអាចឆ្លងកាត់ខ្សែអក្សរហើយសម្រាប់តួអក្សរស្រៈនីមួយៗពីឆ្វេងទៅស្តាំយើងនឹងជំនួសវាដោយតម្លៃខ្ពស់បំផុតនៃជង់។

ក្បួនដោះស្រាយ

  • ទុកតួអក្សរស្រៈទាំងអស់នៅក្នុងសំណុំមួយ។
  • បង្កើតជង់និងរុញតួអក្សរស្រៈទាំងអស់ដែលមាននៅក្នុងខ្សែបញ្ចូលពីឆ្វេងទៅស្តាំ។
  • ឥឡូវឆ្លងកាត់ខ្សែអក្សរម្តងទៀតសម្រាប់តួអក្សរនីមួយៗ។ ប្រសិនបើតួអក្សរបច្ចុប្បន្នគឺស្រៈជំនួសវាដោយតួអក្សរខាងលើនៃជង់ (តួអក្សរស្រៈខាងស្តាំនៃខ្សែបញ្ចូល) ហើយយកវាចេញពីជង់។
  • ត្រឡប់ខ្សែអក្សរដែលបានបម្លែង។

ការអនុវត្តសម្រាប់ស្រៈបញ្ច្រាសនៃដំណោះស្រាយឡេឡេកូដកូដ

កម្មវិធី 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

ការវិភាគស្មុគស្មាញសម្រាប់ស្រៈបញ្ច្រាសនៃដំណោះស្រាយឡេឡេលេខកូដ

ស្មុគស្មាញពេលវេលា

O (N)៖ យើងឆ្លងកាត់ខ្សែអក្សរតែពីរដងប៉ុណ្ណោះ។ ប្រតិបត្ដិការជម្រុញនិងលោតនៅលើជង់ត្រូវការពេលវេលាថេរហើយស្រៈស្រៈមានតែ ១០ ធាតុប៉ុណ្ណោះ (មានន័យថាវាត្រូវការពេលវេលាថេរក្នុងការស្វែងរកតួអក្សរ) ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាគឺ O (N)

ភាពស្មុគស្មាញនៃលំហ 

O (N)៖ នៅជង់អាក្រក់បំផុតអាចមានតួអក្សរទាំងអស់នៃខ្សែបញ្ចូល។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺ O (N) ។

វិធីសាស្រ្ត ២ (ច្រកតែមួយដោយប្រើចង្អុរពីរ)

យើងក៏អាចបញ្ច្រាសស្រៈនៅក្នុងការឆ្លងកាត់តែមួយដោយប្រើទ្រនិចបង្ហាញពីរដោយដោះស្រាយតាមក្បួនដោះស្រាយ៖

  • បង្កើតអថេរពីរ ការចាប់ផ្តើម និង បញ្ចប់ សម្រាប់ចង្អុលទៅស្រៈពីឆ្វេងនិងស្តាំរៀងៗខ្លួន។
  • ផ្តួចផ្តើមជា ការចាប់ផ្តើម= ០ និង បញ្ចប់= ប្រវែង (ខ្សែ) -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 (N) ។

ភាពស្មុគស្មាញនៃលំហ 

O (១)៖ មិនមានកន្លែងទំនេរបន្ថែមត្រូវបានប្រើលើកលែងតែសំណុំស្រៈដែលមានធាតុតែ ១០ ប៉ុណ្ណោះ (មានន័យថាចន្លោះថេរ) ។ ដូច្នេះភាពស្មុគស្មាញនៃលំហគឺ O (១) ។