Mündəricat
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.
