Расшифровать строку от алфавита к целочисленному решению Leetcode


Сложный уровень Легко
Часто спрашивают в эпиграмма Salesforce
строка

Постановка задачи

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

Расшифровать строку от алфавита к целочисленному решению Leetcode

Пример

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», и добавьте его в конструктор струн бакалавр естественных наук
Чтобы преобразовать строку «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 ++ для расшифровки строки от алфавита к целочисленному решению Leetcode

#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 для расшифровки строки от алфавита к целочисленному преобразованию Leetcode Solution

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

Анализ сложности для дешифрования строки от алфавита к целочисленному преобразованию Leetcode Solution

Сложность времени

На): Поскольку мы перемещаем нашу входную строку линейно слева направо, поэтому потребуется время O (n).

Космическая сложность 

На): Мы использовали построитель строк в случае java и строкового потока в cpp. В худшем случае длина будет такой же, как длина входной строки. Таким образом, сложность пространства тоже O (n).