Məktub halının dəyişdirilməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Bloomberg Spotify
Geri qayıtma Parça Bit manipulyasiya Bits SimBaxılıb 40

Məktub halında dəyişdirmə a sim yalnız əlifbalar və rəqəmlərdən ibarətdir, simvoldakı hər bir simvol kiçik və böyük hərflərə çevrilə bilər, simvoldakı hər bir simvolun kiçik və böyük hərflərindən əldə edilə bilən bütün fərqli simləri tapın.

misal

Input: str = “a1b2c3”
Output: a1b2c3, A1b2c3, a1B2c3, a1b2C3, A1B2c3, a1B2C3, A1b2C3, A1B2C3

Input: str = “108”
Output: 108

Input: str = “x”
Output: x, X

Input: str = “T2”
Output: t2, T2

Hərflərin dəyişdirilməsi üçün həll növləri

  1. Dərinlikdən ilk axtarışa əsaslanan geri çəkmə yanaşması.
  2. Genişlik ilk axtarışa əsaslanan yanaşma.

Dərinlik ilk axtarışa əsaslanan geri çəkilmə

Məktub halının dəyişdirilməsi üçün yanaşma

Fikir verilmiş sətirdən hər bir birləşməni dərinlikdə bir şəkildə yaratmaqdır, giriş sətrinin hər bir simvolunu soldan sağa (pos = 0 - pos = str.length () - işləyən bir rekursiv kod tətbiq edirik. 1). Əgər rekursiya zamanı bir nöqtədə str [pos] bir əlifba olarsa, nəticədəki birləşməyə str [pos] -un kiçik və böyük hərflərini əlavə edirik. Lakin, str [pos] rəqəmdirsə, onu kombinasiyaya olduğu kimi əlavə edirik. Sətrin nəticəli birləşməsinin uzunluğu giriş sətrinin uzunluğuna bərabər olduqda rekursiya dayandırılır.

Məktub halının dəyişdirilməsi üçün alqoritm

  1. Boş bir iplə başlayın (deyin s) və sətri soldan sağa emal etməyə başlayın (pos = 0 - pos = giriş sətirinin uzunluğu - 1).
  2. əsas vəziyyəti müəyyənləşdirin: sətir uzunluğu orijinal sətir uzunluğuna bərabər olduqda, indiyə qədər yaradılan sətri çap edin və sonlandırın.
  3. str [pos] ədədi olarsa str [pos] s-ə əlavə edin.
  4. Başqa bir halda str [pos] əlifba olarsa, str [pos] ın kiçik hərfini a-ya əlavə edin nüsxəsi & ayrıca str [pos] in böyük hərfini a-ya əlavə edin nüsxəsi.
  5. pos = giriş sətri uzunluğuna, yəni giriş sətrinin sonuna çatdıqda, indiyə qədər yaradılan sətri çıxarın və rekursiv funksiya çağırışını dayandırın.

Alqoritm aşağıda təsvir edilmişdir:

məktub halının dəyişdirilməsiPin

Həyata keçirilməsi

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void printPermutation(vector <char> str, int pos)
{
    /* on reaching end of the string, print it and return */
    if(pos == str.size())
    {
        for(auto i : str)
        cout<<i;
        
        cout<<endl;
        return;
    }
    
    /* if string character is numeric ignore it and move on to next character */
    if (str[pos] >= '0' && str[pos] <= '9') 
    {
        printPermutation(str, pos + 1);
        return;
    }
    
    /* if string character is alphabet
    1. add the character in lowercase form
    2. add the character in uppercase form
    proceed to next character */
    
    str[pos] = tolower(str[pos]);
    printPermutation(str, pos + 1);
    
    str[pos] = toupper(str[pos]);
    printPermutation(str, pos + 1);
}

int main()
{
    /* input string */
    string input = "a1b2c3";
    /* convert input string to vector of characters for processing */
    vector <char> str(input.begin(),input.end());
    
    printPermutation(str,0);
    return 0;
}
a1b2c3
a1b2C3
a1B2c3
a1B2C3
A1b2c3
A1b2C3
A1B2c3
A1B2C3
Java Proqramı
import java.util.*;
import java.io.*;

class TutorialCup
{
    static void printPermutation(char [] str, int pos)
    {
        /* on reaching end of the string, print it and return */
        if(pos == str.length)
        {
            for(int i=0;i<pos;i++)
            System.out.print(str[i]);
            
            System.out.println();
            return;
        }
        
        /* if string character is numeric ignore it and move on to next character */
        if (str[pos] >= '0' && str[pos] <= '9') 
        {
            printPermutation(str, pos + 1);
            return;
        }
        
        /* if string character is alphabet
        1. add the character in lowercase form
        2. add the character in uppercase form
        proceed to next character */
        
        str[pos] = Character.toLowerCase(str[pos]);
        printPermutation(str, pos + 1);
        
        str[pos] = Character.toUpperCase(str[pos]);
        printPermutation(str, pos + 1);
    }
    
    public static void main (String[] args) 
    {
        /* input string */
        String input = "a1b2c3";
        /* convert input string to vector of characters for processing */
        char [] str = input.toCharArray();
        printPermutation(str,0);
    }
}
a1b2c3
a1b2C3
a1B2c3
a1B2C3
A1b2c3
A1b2C3
A1B2c3
A1B2C3

Məktub halının dəyişdirilməsi üçün mürəkkəblik analizi

  1. T (n) = O (2n), n = giriş sətrinin uzunluğu, 2 əmələ gətiririkn bütün simvol simvolları əlifba olduqda ən pis vəziyyətdə birləşmələr.
  2. A (n) = O (1).

Genişlik ilk axtarış

Məktub halının dəyişdirilməsi üçün yanaşma

Fikir, verilmiş simdən hər bir birləşməni ilk genişlikdə yaratmaqdır. Giriş sətirinin hər bir simvolunu soldan sağa (pos = 0 - pos = str.length () - 1) işləyən bir sıra məlumat strukturundan istifadə edərək təkrarlanan bir kod tətbiq edirik. Təkrarlanma zamanı bir nöqtədə str [pos] bir əlifba olarsa, nəticələnən birləşməyə str [pos] -un kiçik və böyük hərflərini əlavə edirik. Lakin, str [pos] rəqəmdirsə, onu kombinasiyaya olduğu kimi əlavə edirik. Təkrarlama bitdikdən sonra növbənin içindəkiləri çıxardırıq.

Məktub halının dəyişdirilməsi üçün alqoritm

  1. Bir növbə yaradın və içərisinə boş bir simli əlavə edin pos = 0.
  2. Başlayın BFS keçid.
  3. Sıra və mövqe indeksini (= pos) növbədən çıxarın.
  4. bu sətrə str [pos] kiçik və böyük hərfini əlavə edin if str [pos] bir xarakterdir.
    1. Yuxarıda alınan sətrin hər iki versiyasını növbəyə əlavə edin.
  5. Başqa, str [pos] ədədi olarsa, ədədi sətrə əlavə edin.
    1. Sıranı növbəyə əlavə edin.
  6. Keçid sətirinin bütün simvolları işlənənə qədər davam etməlidir. yəni pos = str.length () - 1.
  7. Keçid bitdikdən sonra növbədən bütün ipləri çıxarın.

Alqoritm aşağıda təsvir edilmişdir:

məktub halının dəyişdirilməsiPin

Bu aydındır alqoritm yuxarıda simvollara simvol əlavə etməyimiz lazım deyil, sadəcə əlifbaların soldan sağa hərəkət halını dəyişdiririk.

Həyata keçirilməsi

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void printPermutation(string str)
{
    /* create queue to perform iterative traversal */
    queue <pair<string,int>> q;
    q.push({str,0});
    
    /* begin iterative traversal */
    while(!q.empty())
    {
        /* if we have strings which have been processed upto 
        the last index then terminate the loop */
        if(q.front().second == str.size())
        break;
        
        string str = q.front().first;
        int pos = q.front().second;
        q.pop();
        
        /* if character at index = pos is numeric 
        simply add it to the combination */
        if(str[pos] >= '0' && str[pos] <= '9')
        q.push({str,pos+1});
        
        /* if character at index = pos is alphabet add 
        it's lowercase and uppercase to the combination */
        else
        {
            /* insert string with character at index = pos as it is */
            q.push({str,pos+1});
            
            /* change the case of character at index = pos */
            char ch = str[pos];
            if(islower(ch))
            str[pos] = str[pos] - 32;
            else
            str[pos] = str[pos] + 32;
            
            /* insert string with character at index = pos after changing the case */
            q.push({str,pos+1});
        }
    }
    
    /* after iterative traversal is over print contents of the queue */
    while(!q.empty())
    {
        cout<<q.front().first<<endl;
        q.pop();
    }
}

int main()
{
    /* input string */
    string input = "a1b2c3";
    printPermutation(input);
    return 0;
}
a1b2c3
a1b2C3
a1B2c3
a1B2C3
A1b2c3
A1b2C3
A1B2c3
A1B2C3
Java Proqramı
import java.util.*;
import java.io.*;

class TutorialCup
{
    /* pair class is used to handle pair of 
    StringBuilder and Integer during traversal */
    static class pair
    {
        StringBuilder s;
        int index;
        
        pair(StringBuilder sb,int pos)
        {
            s = new StringBuilder(sb);
            index = pos;
        }
    }
    
    static void printPermutation(StringBuilder s)
    {
        Queue <pair> q = new LinkedList<>();
        q.add(new pair(s,0));
    
        /* begin iterative traversal */
        while(!q.isEmpty())
        {
            /* if we have strings which have been processed upto 
            the last index then terminate the loop */
            if(q.peek().index == s.length())
            break;
            
            pair top = q.poll();
            StringBuilder str = top.s;
            int pos = top.index;
            
            /* if character at index = pos is numeric 
            simply add it to the combination */
            if(Character.isDigit(str.charAt(pos)))
            q.add(new pair(str,pos+1));
            
            /* if character at index = pos is alphabet add 
            it's lowercase and uppercase to the combination */
            else
            {
                /* insert string with character at index = pos as it is */
                q.add(new pair(str,pos+1));
                
                /* change the case of character at index = pos */
                char ch = str.charAt(pos);
                if(Character.isLowerCase(ch))
                str.setCharAt(pos,Character.toUpperCase(ch));
                else
                str.setCharAt(pos,Character.toLowerCase(ch));
                
                /* insert string with character at index = pos after changing the case */
                q.add(new pair(str,pos+1));
            }
        }
        
        /* after iterative traversal is over print contents of the queue */
        while(!q.isEmpty())
            System.out.println(q.poll().s);
    }
    
    public static void main (String[] args) 
    {
        /* input string */
        String input = "a1b2c3";
        /* convert input string to vector of characters for processing */
        StringBuilder str = new StringBuilder(input);
        printPermutation(str);
    }
}
a1b2c3
a1b2C3
a1B2c3
a1B2C3
A1b2c3
A1b2C3
A1B2c3
A1B2C3

Məktub halının dəyişdirilməsi üçün mürəkkəblik analizi

  1. T (n) = O (2n), n = giriş sətrinin uzunluğu, 2 əmələ gətiririkn bütün simvol simvolları əlifba olduqda ən pis vəziyyətdə birləşmələr.
  2. A (n) = O (2n), bütün simli birləşmələri saxlamaq üçün istifadə olunan növbə.

References

Translate »