Chèn thêm số kí tự tối thiểu để xâu có dạng từ a-z

#1

Mọi người cho e xin ý tưởng của code C cho bài này ạ : Nhập 1 xâu vào, chèn thêm tối thiểu kí tự để xâu thành "abcdefghijklmnopqrstuvwxyz"; VD "aiemckgobjfndlhp" có tối thiểu 20 kí tự được chèn thêm. nếu xóa đi 0 hoặc nhiều hơn các ký tự từ xâu đó ta thu được xâu "abcdefghijklmnopqrstuvwxyz", tính số ký tự phải chèn thêm ít nhất (vào bất cứ chỗ nào) để có thể chuyển xâu đó sang dạng "abcdefghijklmnopqrstuvwxyz". Ví dụ : “aiemckgobjfndlhp” thì lược đi còn a c g j l p thì phải chèn thêm 20 kí tự nữa mới đủ ấy ạ

#3

nếu xóa đi 0 hoặc nhiều hơn các ký tự từ xâu đó ta thu được xâu
abcdefghijklmnopqrstuvwxyz, tính số ký tự phải chèn thêm ít nhất (vào bất cứ chỗ nào) để có thể chuyển xâu đó sang dạng abcdefghijklmnopqrstuvwxyz. Ví dụ : aiemckgobjfndlhp thì lược đi còn a c g j l p thì phải chèn thêm 20 kí tự nữa mới đủ ấy ạ

#4

chẳng phải là 26 trừ đi số ký tự hiện có sao?

#5

Ko phải nha. Theo mình thấy có rất nhiều trường hợp cho bài này ấy, để số kí tự còn lại sau khi bớt đi là lớn nhất thì nhiều trường hợp

Mình nghĩ là sẽ tìm số ksi tự tạo thành 1 dãy tăng dài nhất thì số kí tự phải chèn sẽ là nhỏ nhất

#7

Cách giải này thì có vẻ đúng rồi. Không biết bạn gặp khó khăn gì khi hiện thực theo cách này vậy bạn?

3 Likes
#8

Đề có cho xoá bớt character đâu catgun

1 Like
#9

VD cũng là 1 phần trong đề nhé bác :stuck_out_tongue:

3 Likes
#11 
 int maxAscString(string src, int pandding = 0, int min = 0){

    if (pandding == src.length())
        return 0;
    if (src[pandding] <= min)
        return maxAscString(src, pandding + 1, min);

    int m1 = maxAscString(src, pandding + 1, min);
    int m2 = maxAscString(src, pandding + 1, src[pandding]) + 1;
    return max(m1, m2);
}

hoặc

int maxAscString(string src){
    src = char('a'-1) + src + char('z'+1);

    int n = src.length();
    int* len = new int[n]{0};
    for (int i = n-1; i >=0; i--)
        for (int j = i+1; j < n; j++)
            if (src[i] < src[j] && len[i] < len[j] + 1)
                len[i] = len[j] + 1;

    n = len[0]-1;
    delete[] len;
    return n;
}
2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?