Verilmiş Substring-i Rekursiv şəkildə silməklə Stringin Boş ola biləcəyini yoxlayın

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Çiy kərpic Çatdırılma GE Healthcare MakeMyTrip XidmətNow Spotify UHG Optum
SimBaxılıb 241

Problem bəyanat

“Verilən alt sətri rekursiv şəkildə silməklə sətrin boş ola biləcəyini yoxlayın” problemində ikisini verdik strings "S" və "t". Verilən giriş sətri “t” -ləri rekursiv şəkildə silməklə “s” -in tamamilə silinə biləcəyini yoxlamalıyıq.

Qeyd: Verilən alt sətir giriş sətrində olmalıdır.

Giriş Formatı

"T" alt sətrini sildiyimiz "s" simli olan ilk sətir.

"T" simli olan ikinci sətir.

Çıxış formatı

Verilən giriş “t” alt sətrini silməklə “s” -ləri tamamilə silsək “Bəli” yazdırın. Əks təqdirdə “Xeyr” yazdırın.

misal

cocodede
code
Yes

Explanation: Burada kodu bu mövqedən silin co ”code” de, sonra qalan “kodu” sətrdən silin, sonra simli boşalır. Beləliklə, "Bəli" yazdırırıq.

cocoded
code
No

Explanation: Burada kodu “d” co ”kodundan silin, sonra qalan söz cod olur. Beləliklə, onu silmək mümkün deyil, bu səbəbdən də “Xeyr” çıxır.

Alqoritm

Burada STL funksiyalarını find () və silməyi () istifadə edirik.

1. İnput_string keçid.

2. Bir alt simli tapsanız, saxlayın.

3. Alt sətri silin, əgər alt sətir tapılmırsa Xeyr

4. Başqa bir şey, sona çatsa, Bəli qayıdın.

Həyata keçirilməsi

Verilən Substring'i Rekursiv şəkildə silməklə Stringin Boşlaşa biləcəyini Yoxlamaq üçün C ++ proqramı

#include <bits/stdc++.h>

using namespace std;
bool CanBeEmpty(string s, string t)
{
    while(s.size()>0)
    {
        int index = s.find(t);
        if (index == -1)
        {
            break;
        }
        s.erase(index, t.size());
    }
    if(s.size() == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}
 
int main()
{
    string s,t;
    cin>>s>>t;
    if(CanBeEmpty(s,t))
    {
        cout<<"Yes";
    }
    else
    {
        cout<<"No";
    }
    return 0;
}

Verilən Substring-i Rekursiv Silməklə Stringin Boşlaşa biləcəyini Yoxlamaq üçün Java proqramı

import java.util.Arrays;
import java.util.Scanner;

class sum {
    
    static boolean check(String s, String t) 
    { 
        while(s.length() > 0) 
        {  
            int idx = s.indexOf(t); 
            if(idx == -1) 
            { 
                break; 
            } 
            s = s.replaceFirst(t,""); 
        } 
        return(s.length() == 0); 
    }
    public static void main(String[] args) 
    {
        Scanner sr= new Scanner(System.in);
        String s = sr.next();
        String t = sr.next();
        if(check(s,t))
        {
            System.out.println("Yes");
        }
        else
        {
            System.out.println("No");
        }
    } 
}
abcabcdede
abcde
Yes

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (n ^ 2) hara n "s" simli ölçüsüdür. Burada alt sətri yoxlayırıq və “t” alt sətri üçün hər axtarış və silmə üçün xətti vaxt aparan s sətrindən silirik.

Kosmik Mürəkkəblik

O (1) çünki burada heç bir köməkçi yerdən istifadə etmirik.

Translate »