Scramble String LeetCode Həlli

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Çiy kərpic Amazon alma Facebook YahooBaxılıb 26

Problem bəyanat

Scramble String LeetCode Solution – Aşağıdakı alqoritmdən istifadə edərək t sətrini əldə etmək üçün s sətrini sındıra bilərik:

  1. Əgər simin uzunluğu 1-dirsə, dayandırın.
  2. Sətin uzunluğu > 1 olarsa, aşağıdakıları edin:
    • Sətri təsadüfi indekslə iki boş olmayan alt sətirə bölün, yəni sətir s, bölün x və y hara s = x + y.
    • Təsadüfi iki alt sətri dəyişdirmək və ya onları eyni qaydada saxlamaq qərarına gəlir. yəni bu addımdan sonra s ola bilər s = x + y or s = y + x.
    • 1-ci addımı iki alt sətirin hər birinə rekursiv olaraq tətbiq edin x və y.

İki sim verilir s1 və s2 of eyni uzunluqda, qayıt true if s2 nin şifrələnmiş simidir s1, əks halda qayıt false.

Input: s1 = "great", s2 = "rgeat"
Output: true
Explanation: One possible scenario applied on s1 is:
"great" --> "gr/eat" // divide at random index.
"gr/eat" --> "gr/eat" // random decision is not to swap the two substrings and keep them in order.
"gr/eat" --> "g/r / e/at" // apply the same algorithm recursively on both substrings. divide at random index each of them.
"g/r / e/at" --> "r/g / e/at" // random decision was to swap the first substring and to keep the second substring in the same order.
"r/g / e/at" --> "r/g / e/ a/t" // again apply the algorithm recursively, divide "at" to "a/t".
"r/g / e/ a/t" --> "r/g / e/ a/t" // random decision is to keep both substrings in the same order.
The algorithm stops now, and the result string is "rgeat" which is s2.
As one possible scenario led s1 to be scrambled to s2, we return true.

Izahat

Əsas ideya s1(s2)-ni k və len-k uzunluğunda iki alt sətirə bölmək və iki alt sətirin s1[0..k-1] və s1[k, len-1] s2[-nin skramblları olub olmadığını yoxlamaqdır. 0..k-1] və s2[k,len-1] və ya s2[len-k, len-1] və s2[0..len-k-1] rekursiya vasitəsilə. Bir çox təkrarlanan rekursiv funksiya çağırışlarına görə düz rekursiya çox yavaş olacaq. Rekursiyanı sürətləndirmək üçün aralıq nəticələri saxlamaq üçün unordered_map isScramblePair istifadə edə bilərik. Burada istifadə olunan açar s1+s2-dir, lakin digər düymələr də mümkündür (məsələn, indekslərdən istifadə etməklə)

The rekursiv versiya eksponensial mürəkkəbliyə malikdir. Performansı daha da yaxşılaşdırmaq üçün O(N^4) mürəkkəbliyi olan aşağıdan yuxarı DP-dən istifadə edə bilərik. Burada s1[i..i+len-1]-nin s2[j..j+len-1] skrambl olub-olmadığını göstərən isS[len][i][j] cədvəli qururuq.

Bundan əlavə, bir çox hallarda biz budama ilə rekursiyamızı erkən dayandıra biləcəyimizi gördük: yəni ilk olaraq rekursiya etməzdən əvvəl s1 və s2-nin eyni simvol dəstinə malik olub-olmadığını yoxlamaqla: əgər yoxsa, sadəcə rekursiya olmadan dayandırın. Bu müşahidə bizi aşağıdakı Recursion+cache+budama versiyasına aparır. Burada önbelleğin açarı idx1-ə dəyişirsSize +idx2 + lensSize*sSize;

Kodu

Scramble String üçün C++ kodu

class Solution {
private:
    bool DP_helper(string &s1, string &s2, int idx1, int idx2, int len, char isS[])
    {
        int sSize = s1.size(),i, j, k, hist[26] , zero_count =0;
        if(isS[(len*sSize+idx1)*sSize+idx2]) return isS[(len*sSize+idx1)*sSize+idx2]==1;
        bool res = false;
        
        fill_n(hist, 26, 0);
        for(k=0; k<len;++k)
        { // check if s1[idx1:idx1+len-1] and s2[idx2:idx2+len-1] have same characters
            zero_count +=  (0==hist[s1[idx1+k]-'a']) - (0== ++hist[s1[idx1+k]-'a']);
            zero_count +=  (0==hist[s2[idx2+k]-'a']) - (0== --hist[s2[idx2+k]-'a']);
        }
        if(zero_count) {isS[(len*sSize+idx1)*sSize+idx2] = 2; return false;} //if not, return directly
        if(len==1)     {isS[(len*sSize+idx1)*sSize+idx2] = 1; return true;}
        for(k=1;k<len && !res;++k) //otherwise, recursion with cache
        {
            res = res || (DP_helper(s1, s2, idx1, idx2, k, isS) && DP_helper(s1, s2, idx1+k, idx2+k, len-k, isS) );
            res = res || (DP_helper(s1, s2, idx1+len-k, idx2, k, isS) && DP_helper(s1, s2, idx1, idx2+k, len-k, isS) );
        }
        isS[(len*sSize+idx1)*sSize+idx2] = res?1:2;
        return res;
    }
public:
    bool isScramble(string s1, string s2) {
        const int sSize = s1.size();
        if(0==sSize) return true;
        char isS[(sSize+1)*sSize*sSize];
        fill_n(isS, (sSize+1)*sSize*sSize, 0);
        return DP_helper(s1, s2, 0, 0, sSize, isS);
    }
};

Scramble String üçün Java Kodu

public class Solution {
    public boolean isScramble(String s1, String s2) {
        if (s1.equals(s2)) return true; 
        
        int[] letters = new int[26];
        for (int i=0; i<s1.length(); i++) {
            letters[s1.charAt(i)-'a']++;
            letters[s2.charAt(i)-'a']--;
        }
        for (int i=0; i<26; i++) if (letters[i]!=0) return false;
    
        for (int i=1; i<s1.length(); i++) {
            if (isScramble(s1.substring(0,i), s2.substring(0,i)) 
             && isScramble(s1.substring(i), s2.substring(i))) return true;
            if (isScramble(s1.substring(0,i), s2.substring(s2.length()-i)) 
             && isScramble(s1.substring(i), s2.substring(0,s2.length()-i))) return true;
        }
        return false;
    }
}

Scramble String LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi

O (mn)

Kosmik Mürəkkəblik

O (mn)

Translate »