Ən Qısa Uzunluqlu LeetCode Həlli ilə Kodlanmış Sətir

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon google microsoft
HuaweiBaxılıb 24

Problem bəyanat

Ən Qısa Uzunluqlu Kodlanmış Sətir LeetCode Həlli – Sətir verilmişdir s, sətri elə kodlayın ki, onun kodlaşdırılmış uzunluğu ən qısa olsun.

Kodlaşdırma qaydası belədir: k[encoded_string], Harada encoded_string kvadrat mötərizə içərisində tam olaraq təkrarlanır k dəfə. k müsbət tam ədəd olmalıdır.

Əgər kodlaşdırma prosesi sətri qısaltmırsa, onu kodlamayın. Bir neçə həll yolu varsa, geri qayıdın onlardan hər hansı biri.

Input: s = "aaa"
Output: "aaa"
Explanation: There is no way to encode it such that it is shorter than the

giriş sətri

, so we do not encode it.

Izahat

Ümumi fikirlər:

Biz 2 ölçülü yaddaşdan istifadə edirik dp[first][count] -nin ən qısa kodlanmış sətirini saxlamaq üçün s[first ... first+count-1]. Ona görə də bizim son məqsədimiz tapmaqdır dp[0][N], Harada N uzunluğu s.

Hər biri üçün first və countdp[first][count] aşağıdakı iki vəziyyətdən biri olmalıdır:

  • Case 1: dp[first][count] şəklindədir k[***]. Bu halda, dp[first][count] tərəfindən yaradıla bilər alt sətri təkrarlamaq.
  • Case 2: dp[first][count] şəklində DEYİL k[***]. Bu halda, dp[first][count] iki alt sətri birləşdirməklə yaradıla bilər. İki alt sətirin uzunluğu olsun count1 və count - count1, bizdə vardp[ilk][count] = dp[ilk][count1] + dp[ilk+count1][count - count1]

Yekun məqsədimizi hesablamaq üçün 2-ci işin təhlilinə görə dp[0][N], istifadə etməmiz lazım ola bilər dp[first][count] (0<=first<N1<=count<=N-first). Bu dəyərlərdən istifadə edərkən biz yadda saxlanılandan istifadə edirik dinamik proqramlaşdırma.

  • If dp[first][count] əvvəllər hələ hesablanmamışdır, o, standart dəyərə bərabərdir (yəni boş sətir). Bu vəziyyətdə hesablayırıq dp[first][count] Buna görə.
  • If dp[first][count] əvvəl hesablanmışdır, standart dəyərə bərabər deyil. Bu vəziyyətdə hesablamağa ehtiyac yoxdur dp[first][count].

Kodu

Ən Qısa Uzunluqda Kodlanmış Sətir üçün Java Kodu

class Solution {

public String encode(String s) {
    String[][] dp = new String[s.length()][s.length()];
    
    for(int l=0;l<s.length();l++) {
        for(int i=0;i<s.length()-l;i++) {
            int j = i+l;
            String substr = s.substring(i, j+1);
            // Checking if string length < 5. In that case, we know that encoding will not help.
            if(j - i < 4) {
                dp[i][j] = substr;
            } else {
                dp[i][j] = substr;
                // Loop for trying all results that we get after dividing the strings into 2 and combine the   results of 2 substrings
                for(int k = i; k<j;k++) {
                    if((dp[i][k] + dp[k+1][j]).length() < dp[i][j].length()){
                        dp[i][j] = dp[i][k] + dp[k+1][j];
                    }
                }
                
                // Loop for checking if string can itself found some pattern in it which could be repeated.
                for(int k=0;k<substr.length();k++) {
                    String repeatStr = substr.substring(0, k+1);
                    if(repeatStr != null 
                       && substr.length()%repeatStr.length() == 0 
                       && substr.replaceAll(repeatStr, "").length() == 0) {
                          String ss = substr.length()/repeatStr.length() + "[" + dp[i][i+k] + "]";
                          if(ss.length() < dp[i][j].length()) {
                            dp[i][j] = ss;
                          }
                     }
                }
            }
        }
    }
    
    return dp[0][s.length()-1];
}
}

Ən Qısa Uzunluqda Kodlanmış Sətir üçün Python Kodu

class Solution:
    
    def encode(self, s: str) -> str:
        memo = {}
        return self._get_encoded_str(s, memo)
    
    def _get_encoded_str(self, s, memo):
        if s == "" or len(s) < 5:
            return s
        if s in memo:
            return memo[s]
        chosen_str = s
        min_len = len(s)
        for i in range(1, len(s)//2 + 1):
            encoded_str = s
            prefix = s[:i]
            suffix = s[i:]
            prefix_count = self._get_prefix_count(prefix, suffix)
            encoded_prefix = self._get_encoded_str(prefix, memo)
            encoded_suffix = self._get_encoded_str(suffix, memo)
            if prefix_count > 0:
                k = prefix_count * len(prefix)
                encoded_suffix_from_k = self._get_encoded_str(suffix[k:], memo)
                encoded_str = str(prefix_count + 1) + "[" + encoded_prefix + "]" + encoded_suffix_from_k
            encoded_part_str = encoded_prefix + encoded_suffix 
            if len(encoded_str) > len(encoded_part_str):
                encoded_str = encoded_part_str
            if min_len > len(encoded_str):
                chosen_str = encoded_str
                min_len = len(encoded_str)
        memo[s] = chosen_str
        return chosen_str

    """
    Helper method finds the count of prefix in suffix.
    """
    def _get_prefix_count(self, prefix, suffix):
        count = 0
        i = 0
        while i < len(suffix):
            j = suffix.find(prefix, i)
            if i != j:
                break
            count += 1
            i = j + len(prefix)
        return count

Ən Qısa Uzunluqlu LeetCode Həlli ilə Kodlanmış Sətir üçün Mürəkkəblik Təhlili

Saat: O (N ^ 3)
hər bir dəyəri yeniləyin dp[first][count] ən çox O(N) vaxt tələb edir.
O(N^2) belə qiymətlər var.
Beləliklə, ümumi zaman mürəkkəbliyi O(N^3) təşkil edir.

Space: O (N ^ 2)
Məkanı dp[][] O(N^2) olur.

Referans: https://en.wikipedia.org/wiki/Dynamic_programming

Şərh yaz

Translate »