فك تشفير سلسلة من الأبجدية إلى حل Leetcode لرسم الخرائط بشكل صحيح


مستوى الصعوبة سهل
كثيرا ما يطلب في سخرية ساليسفورسي
خيط

المشكلة بيان

في هذه المشكلة ، حصلنا على سلسلة تحتوي على أرقام (0-9) و "#". علينا تحويل هذه السلسلة إلى سلسلة من الأحرف الإنجليزية الصغيرة باستخدام التعيين التالي.

فك تشفير سلسلة من الأبجدية إلى حل Leetcode لرسم الخرائط بشكل صحيح

مثال

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

التفسير:

"10 #" -> "j" ، "11 #" -> "k" ، "1" -> "a" ، "2" -> "b".

s = "1326#"
"acz"

التفسير:

"1" -> "أ" ، "3" -> "ج" ، "26 #" -> "ض".

الرسالة

يمكننا أن نرى أنه علينا فقط القلق بشأن "#". عندما نجتاز السلسلة المعطاة من اليسار إلى اليمين باستخدام العداد (دعنا 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 ، يمكننا القول أنه إذا كان الحرف في 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 لرسم الخرائط عدد صحيح

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 لرسم الخرائط بشكل صحيح

تعقيد الوقت

على): نظرًا لأننا نجتاز سلسلة الإدخال الخاصة بنا خطيًا من اليسار إلى اليمين ، فسيتم أخذ وقت O (n).

تعقيد الفضاء 

على): لقد استخدمنا منشئ السلاسل في حالة java و string stream في cpp. في أسوأ الحالات ، سيكون الطول هو نفسه طول سلسلة الإدخال. وبالتالي ، فإن تعقيد الفضاء هو أيضًا O (n).