Təkrarlanan alt sətir nümunəsi LeetCode Həlli

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Facebook google SalesforceBaxılıb 25

Problem bəyanat

Təkrarlanan alt sətir nümunəsi LeetCode Həlli – Sətir verilir s, onun alt sətirini götürərək və alt sətirin bir neçə nüsxəsini birlikdə əlavə etməklə onun tikilə biləcəyini yoxlayın.

Input: s = "abab"
Output: true
Explanation: It is the substring "ab" twice.

Izahat

  1. Giriş sətirinin ilk simvolu təkrarlanan alt sətirin ilk simvoludur
  2. Giriş sətirinin son simvolu təkrarlanan alt sətirin sonuncu simvoludur
  3. Qoy S1 = S + S (giriş sətirində S)
  4. S1-in 1 və son simvolunu silin. Bu S2 olsun
  5. Əgər S S2-də mövcuddursa, onda doğru, əksinə yalan qaytarın
  6. S-in başladığı, sonra təkrarlanan alt sətir uzunluğu i + 2 və təkrarlanan alt sətir S[1: i+0] olduğu S1-də i indeksi olsun.

Müşahidələr:

1. Təkrarlanacaq alt sətir təkrarlanmalıdır ən azı 2 dəfə əks halda hər sətir təkrarlanan alt sətir kimi qəbul ediləcək.
2. Təkrarların sayı arasında olduğundan n dəfə (sətin ölçüsü) 2 dəfə belə bir ölçüsü etibarlıdır təkrarlanan alt sətir arasında qalacaqdı    [ 1, n / 2 ].
3. ” i ” ölçülü alt sətir yalnız əgər təkrarlanan alt sətir olacaq ölçü % i == 0.
4. İndi iki üsulumuz var ki, k ölçüsündə cari alt sətir təkrarlanan alt sətirdir, ya yox:-

A yanaşması:

  1. i = 1-dən i = n/2-ə qədər bir döngə keçirin.
  2. Hər bir “i” dəyəri üçün biz curr alt sətrini 0-dan i-yə kimi saxlaya və j = i dəyişənini işə sala bilərik.
  3. İndi isə (j
  4. əgər j==s.length() doğru qaytarır // biz sona çatdı əlavə edərkən sətirdən.
  5. false qaytarın // şərtə uyğun ölçü alt sətri yoxdur.

B yanaşması:

3-cü addımda hər bir alt sətri yoxlamaq əvəzinə, təkrarlanan alt sətir s.length() / i dəfələri nəzərə alaraq yeni sətir yaradacağıq.

 

Kodu

Təkrarlanan alt sətir nümunəsi üçün C++ kodu

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        
        string ans="",temp="",res="";
        
        for(int i=0;i<s.length()-1;i++)
        {
            temp+=s[i];
            if(s.length()%temp.length()==0)
            {
                res="";
                for(int j=1;j<=int(s.length()/temp.length());j++)
                    res+=temp;
                if(res==s)
                    return 1;
            }
            
        }
            
        return 0;
    }
};

Təkrarlanan alt sətir nümunəsi üçün Python kodu

class Solution:
    def repeatedSubstringPattern(self, s: str) -> bool:
        
        ans=""
        temp=""
        
        for i in range(0,len(s)-1):
            temp+=s[i]
            if  len(s)%len(temp)==0 and temp*int((len(s)/len(temp)))==s:
                print(temp)
                return 1
        
        return 0

Təkrarlanan alt sətir nümunəsi üçün Java kodu

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        for (int size=1;size<=s.length()/2;size++) {
            if (s.length()%size==0) {
                String curr=s.substring(0,size);
                int j=size;
                while (j<s.length() && s.substring(j,j+size).equals(curr)) {
                    j+=size;
                }
                if (j==s.length()) return true;
            }
        }
        return false;
        
    }
}

Təkrarlanan Substring Pattern LeetCode Həlli üçün Mürəkkəblik Təhlili

Zamanın mürəkkəbliyi: O (n ^ 2)

Kosmik Mürəkkəblik: O (1)

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

Şərh yaz

Translate »