Розшифруйте рядок з алфавіту до цілочисельного зіставлення рішення штрих-коду


Рівень складності Легко
Часто запитують у Шлях Salesforce
рядок

Постановка проблеми

У цій задачі ми отримуємо рядок, що містить цифри (0-9) та '#'. Ми повинні перетворити цей рядок на рядок з малих англійських букв, використовуючи наступне відображення.

Розшифруйте рядок з алфавіту до цілочисельного зіставлення рішення штрих-коду

Приклад

s = "10#11#12"
"jkab"

Пояснення:

“10 #” -> “j”, “11 #” -> “k”, “1” -> “a”, “2” -> “b”.

s = "1326#"
"acz"

Пояснення:

“1” -> “a”, “3” -> “c”, “26 #” -> “z”.

Підхід

Ми бачимо, що нам просто потрібно турбуватися про "#". Коли ми обходимо заданий рядок зліва направо за допомогою лічильника (let i), тоді для кожного індексу i (0 <= i <= n-3) нам просто потрібно перевірити, чи символ біля наступного індексу від i тобто символ з індексом i + 2 дорівнює "#".

Для кожного i (від 0 до n-3), якщо символ з індексом i + 2 дорівнює '#', тоді об'єднайте цей індекс i з i + 1 і сформуйте символ, використовуючи ці дві цифри.
наприклад, “12 #”, якщо ми переходимо рядок зліва направо, ми бачимо, що коли i = 0, то символ з індексом i + 2 дорівнює '#'. Таким чином, комбінуйте цифри, присутні в індексах i та i + 1, тобто комбінуйте цифри 1 та 2, зробіть їх “12”. Тепер перетворіть 12 на його відображення символів, тобто "l", і додайте його в струнбудівник sb.
Щоб перетворити рядок «12» у символ «l», ми створили функцію перетворення, яка приймає число у форматі рядка та перетворює його у відповідний символ.
І якщо символ з індексом i + 2 не є "#", тоді ми не повинні поєднувати символ в індексі i з символом в індексі i + 1.

наприклад, "123", якщо ми бачимо з індексу i = 0, індекс i + 2, тобто символ у 2 не є "#", таким чином, ми просто додамо перетворення символів "1" у нашій відповіді.

Для символу з індексами n-2 та n-1 ми можемо сказати, що якщо char у n-1 буде вже "#", то ми не будемо виходити з циклу після індексу n-3, інакше обидва символи в n-2 і n-1 повинні бути відображені окремо.

Реалізація

Програма C ++ для розшифровки рядка з алфавіту до цілочисельного зіставлення рішення штрих-коду

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

char convert(string str){
    stringstream ss(str);
    int num;
    ss>>num;
    return num+96;
}

string freqAlphabets(string s) {
        stringstream ss;
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s[i+2]=='#'){
                ch=(char)convert(s.substr(i, 2) );
                i+=2;
            }else{
                ch=(char)convert(s.substr(i,1));
            }
            i++;
            ss<<ch;
        }
        while(i<s.length()){
            char ch=(char)convert(s.substr(i,1));
            ss<<ch;
            i++;
        }
        
        return ss.str();
    }

int main()
{
    cout << freqAlphabets("1326#") ;
}
acz

Програма Java для розшифровки рядка з алфавіту до цілочисельного зіставлення рішення штрих-коду

import java.util.*;
import java.lang.*;

class Rextester
{  
    public static String freqAlphabets(String s) {
        StringBuilder sb=new StringBuilder();
        int i=0;
        while(i<s.length()-2){
            char ch;
            if(s.charAt(i+2)=='#'){
                ch=(char)convert(s.substring(i,i+2));
                i+=2;
            }else{
                ch=(char)convert(s.substring(i,i+1));
            }
            i++;
            sb.append(ch);
        }
        while(i<s.length()){
            char ch=(char)convert(s.substring(i,i+1));
            sb.append(ch);
            i++;
        }
        
        return sb.toString();
    }
    
    
    public static int convert(String str){
        int num=Integer.parseInt(str);
        return num+96;
    }

    public static void main(String args[])
    {
        System.out.println(freqAlphabets("10#11#12"));
    }
}
jkab

Аналіз складності для розшифровки рядка з алфавіту до цілочисельного відображення рішення штрих-коду

Складність часу

O (n): Оскільки ми обводимо наш вхідний рядок лінійно зліва направо, таким чином буде братися час O (n).

Складність простору 

O (n): Ми використовували конструктор рядків у випадку Java та потокового рядка в cpp. У гіршому випадку тоді довжина буде такою ж, як довжина вхідного рядка. Таким чином, космічна складність теж є O (n).