Bài tập biến đổi xâu c++

#1

image
image1306×546 27.5 KB

mọi người cho e hỏi bài này với ạ, ý tưởng của em là sẽ check từng kí tự của xâu B xem có xuất hiện theo đúng thứ tự trong xâu A không, sẽ check những phần tử còn lại trong xâu A xem có là chữ in thường hết không, nếu thỏa mãn cả 2 thì sẽ biến đổi được nhưng submit thì lại sai nên chắc logic của e đã sai, đây là code của em ạ
bien doi xau text code | WTOOLS

#include<iostream>
using namespace std;
int main(){
    int Q;
    cin>>Q;
    while (Q){
    string a;
    string b;
    cin>>a;
    cin>>b;
    int tmpIndex=-1;
    int cnt=0;
    for (int i=0;i<b.length();i++){
        for (int j=0;j<a.length();j++){
            if (b[i]==a[j]||b[i]==a[j]-32){
                if (j>tmpIndex){
                cout<<a[j]<<" ";
                a[j]='0';
                cnt++;
                tmpIndex=j;
                break;
                }
                
            }
        }
    }
    int cnt1=0;
    if (cnt==b.length()){
        for (int i=0;i<a.length();i++){
            if (a[i]!='0'&&a[i]>='a'&&a[i]<='z'){
                cnt1++;
            }
        }
        if (cnt1==a.length()-b.length()){
            cout<<"YES"<<endl;
        }
        else cout<<"NO"<<endl;
    }
    else cout<<"NO"<<endl;
    Q--;
    }
    return 0;
}
#2

Đọc sơ qua thì có vẻ như code của bạn sẽ bị sai với input:

1
abcAbc
AB
2 Likes
#3

bump ạ hiuhiu…

#4

Nếu xâu A toàn chữ in hoa, bạn có kiểm tra được các chữ cái trong xâu B có nằm trong & đảm bảo thứ tự trong xâu A không?

#5

chà không biết ngừi anh em làm xong chưa :>
nếu chưa xong thì tôi có thể gợi ý là dùng 3 vòng for để kiểm tra từng chữ in hoa và kiểm tra từng chữ in thường nhé
hoặc bro có thể tham khảo bài đồng xu trong quy hoạch động để giải nhưng có lẽ logic 2 dạng này thì vẫn khá là giống nhau

#6

Kiểm tra chữ in hoa và thường chỉ cần 1 vòng lặp là đủ.

1 Like
#7

nhưng 1 vòng for làm sao ông kiểm tra được các trường hợp viết hoa chữ cái

#8

Tại vị trí 1 ký tự có 3 khả năng:

  • Viết hoa nó nếu nó là ký tự thường
  • Bỏ qua ký tự đó nếu nó là ký tự thường
  • Xét ký tự đó nếu nó là ký tự hoa

Vậy nên 1 if là đủ.

1 Like
#9

Xem ra tôi lạm dụng vòng for quá :>
cảm ơn ông nma tôi vẫn có suy nghĩ là chí ít cũng phải 1 vòng for cho số bộ test, 1 vòng for để duyệt xâu , liệu ông có thể gửi giải pháp sử dụng ít vòng lặp của ông không

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    string a,b;
    for(int i=0;i<n;i++) {
        cin >> a >> b;
        int sl=0, ktra=0, k=0;
        if(a.size()<b.size())   cout<<"NO"<<endl;
        else{
        for(int j=0;j<b.size();j++){            //kiem tra tung chu in hoa
          for(int h=k;h<a.size();h++){
             if(a[h]==b[j]) {
                 k=h+1;ktra++;
                 a[h]=' ';b[j]=' ';
                 break;
                 }
             }}
             k=0;
        for(int j=0;j<b.size();j++){            //kiem tra tung chu in thuong
          for(int h=k;h<a.size();h++){
             if(a[h]!=' '&&b[j]!=' '&&a[h]==char(b[j]+32)) {
                 k=h+1;
                 ktra++;
                 a[h]=' ';b[j]=' ';
                 break;
             }}}
       
        if(ktra!=b.size())  cout<<"NO"<<endl;
       
        else{
            bool ktra2=true;
            for(int l=0;l<a.size();l++){
                if(a[l]<='Z'&&a[l]>='A') {
                    ktra2=false;
                    break;
            }}
            if(ktra2) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }}}
    return 0;
}

hoặc sử dụng:

#include <bits/stdc++.h>
using namespace std;
bool kiemtra(string s1, string s2)
{
    int n = s1.size();
    int m = s2.size();
    bool ds[n + 1][m + 1];
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            ds[i][j] = false;
        }}ds[0][0] = true;
    for (int i = 0; i < s1.size(); i++) {
        for (int j = 0; j <= s2.size(); j++) {
            if (ds[i][j]) {
                if (j < s2.size() && (toupper(s1[i]) == s2[j]))
                    ds[i + 1][j + 1] = true;
                if (!isupper(s1[i]))
                    ds[i + 1][j] = true;
            }}}
    return (ds[n][m]);
}
int main()
{  
    string s1;
    string s2;
    int n;
    cin >> n;
    for (int i = 0; i < n ;i++){
        cin>>s1>>s2;
        if (kiemtra(s1, s2))
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}
1 Like
#10

Mình chỉ nhắc đến số vòng for kiểm tra cho 1 test case, nếu muốn nhiều test case thì tất nhiên phải có 1 vòng for các test case ở ngoài rồi chứ bạn.

3 Likes
#11

code đầu của b có vẻ sai với test này hsao ý
acB
ABC

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?