Дешифриране на низ от азбука до решение за цялостно картографиране на Leetcode


Ниво на трудност Лесно
Често задавани в шикалкавене Salesforce
Низ

Декларация за проблема

В този проблем ни се дава низ, съдържащ цифри (0-9) и '#'. Трябва да преобразуваме този низ в низ с малки букви на английски, като използваме следното картографиране.

Дешифриране на низ от азбука до решение за цялостно картографиране на Leetcode

Пример

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

Обяснение:

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

s = "1326#"
"acz"

Обяснение:

„1“ -> „а“, „3“ -> „в“, „26 #“ -> „z“.

Подход

Виждаме, че просто трябва да се тревожим за „#“. Когато прекосим дадения низ отляво надясно с помощта на брояч (нека 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 програма за дешифриране на низ от азбука до цялостно картографиране на Leetcode решение

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) време.

Сложност на пространството 

На): Използвали сме конструктор на низове в случай на Java и низ потоци в cpp. В най-лошия случай дължината ще бъде същата като дължината на входния низ. По този начин сложността на пространството също е O (n).