Xuất các từ trong chuỗi, mỗi từ một dòng

Nguồn: Góp ý code học viên Độ khó: Dễ Xâu Xử lý xâu Nhập môn

Đề bài

(Bài tập xử lý chuỗi mình góp ý code cho một bạn học viên, mình phát biểu lại cho rõ ràng như sau.)

Cho một chuỗi $s$ gồm các từ, các từ cách nhau bởi một hoặc nhiều khoảng trắng; đầu chuỗi và cuối chuỗi cũng có thể có khoảng trắng thừa. Một từ là một dãy liên tiếp các ký tự khác khoảng trắng.

Yêu cầu: Xuất các từ trong chuỗi theo thứ tự xuất hiện, mỗi từ nằm trên 1 dòng (không có dòng trống nào chen giữa).

Dữ liệu vào: Một dòng duy nhất là chuỗi $s$ ($1 \le$ độ dài $\le 1000$), chứa ít nhất một từ.

Kết quả: Mỗi từ trên một dòng.

Ví dụ 1 – input

Nam Son

Ví dụ 1 – output

Nam
Son

Ví dụ 2 – input (có khoảng trắng thừa)

   Nam     Son      

Ví dụ 2 – output

Nam
Son

Lời mở đầu

Hôm nay mình chia sẻ một bài tập xử lý chuỗi rất cơ bản: xuất các từ trong chuỗi, mỗi từ nằm trên 1 dòng. Bài này mình góp ý code cho một em học viên và phân tích hướng dẫn em cách làm tốt hơn 🤗. Tuy cơ bản nhưng qua bài này các bạn sẽ thấy được cách mình "bắt bệnh" một đoạn code: chạy đúng với trường hợp đẹp chưa đủ, phải nghĩ tiếp xem lỡ dữ liệu "xấu" thì sao, rồi còn phải soi luôn cả chỗ truy xuất mảng có hợp lệ không nữa.

Bạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì link bài đây nhé:

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Giải thích ví dụ: với chuỗi "Nam Son" thì có 2 từ là Nam và Son, in mỗi từ trên một dòng. Với chuỗi " Nam Son " thì dù đầu chuỗi, giữa 2 từ và cuối chuỗi có bao nhiêu khoảng trắng đi nữa, kết quả vẫn chỉ là đúng 2 dòng Nam và Son.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Gặp khoảng trắng là xuống dòng · chỉ đúng với chuỗi chuẩnCách 2Xét thêm ký tự liền trước · đúng với mọi chuỗi

Cách 1Gặp khoảng trắng là xuống dòng – O(N)

Ý tưởng thì nó quá cơ bản để nhìn thấy. Giả sử ta có chuỗi "Nam Son" đi hen: nếu chuỗi được chuẩn như thế này, không thừa khoảng trắng gì cả, thì đơn giản mình nhìn thấy vấn đề rất rõ, là:

Ý tưởng

Duyệt từng ký tự: cứ gặp ký tự khác khoảng trắng thì mình in ra, gặp ký tự khoảng trắng thì mình xuống dòng.

Source code để các bạn tham khảo nếu làm theo hướng này (code của mình trong bài dùng chuỗi gán sẵn và system("pause") để demo trên Visual Studio, ở đây mình đổi sang đọc chuỗi bằng cin.getline và bỏ system("pause") để các bạn chạy/nộp cho tiện):

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char s[1005];
    cin.getline(s, 1005);
    int length = strlen(s);

    for(int i = 0; i < length; ++i)
    {
        if(s[i] != ' ')
            cout << s[i];
        else
            cout << endl;
    }

    return 0;
}

s = input()
length = len(s)

for i in range(length):
    if s[i] != ' ':
        print(s[i], end='')
    else:
        print()

Đó là trong trường hợp chuỗi được chuẩn, không bị khoảng trắng dư gì hết. Giờ lỡ chuỗi bị nhiều khoảng trắng dư thì sao? Các bạn thử bấm nút "Nam     Son" trong khung chạy tay bên dưới xem nhé:

C++▶ Chạy tay từng dòng codeCách 1: in ký tự khác khoảng trắng, gặp khoảng trắng thì xuống dòng (endl).

Dữ liệu vào (stdin) – sửa thoải máiNam Son

Dữ liệu mẫu:

1#include <iostream>

2#include <string.h>

3using namespace std;

4

5int main()

6{

7 char s[1005];

8 cin.getline(s, 1005);

9 int length = strlen(s);

10

11 for(int i = 0; i < length; ++i)

12 {

13 if(s[i] != ' ')

14 cout << s[i];

15 else

16 cout << endl;

17 }

18

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Dư khoảng trắng là xuống dòng liên tục

Lúc này vì bị dư nhiều khoảng trắng giữa 2 từ nên nó mới liên tục bị xuống dòng nhiều lần, tạo ra các dòng trống chen giữa Nam và Son. Khoảng trắng ở đầu chuỗi cũng tạo ra các dòng trống ở trên cùng. Vậy là cách này chỉ đúng với chuỗi chuẩn.

Đánh giá độ phức tạp: duyệt chuỗi đúng một lần nên thời gian $O(N)$ với $N$ là độ dài chuỗi, bộ nhớ $O(N)$ để chứa chuỗi.

Không gian$O(N)$

Thời gian$O(N)$

Cách 2Xét thêm ký tự liền trước – O(N)

Vậy giờ mình làm sao để với chuỗi là "Nam Son" hay " Nam Son" hay "Nam Son " nó đều in ra 2 dòng duy nhất là Nam và Son? Tức là với code đang có, sửa lại làm sao để dù nó có nhiều khoảng trắng thì nó vẫn ra đúng cái mình cần?

Bước 1: chỉ xuống dòng khi ký tự trước đó khác khoảng trắng

Mấu chốt nằm ở chỗ: khi gặp ký tự s[i] là khoảng trắng, thay vì như hiện tại mình cout << endl; xuống dòng luôn, thì mình sẽ cần 1 bước kiểm tra xem ký tự mình vừa xử lý trước đó:

• Nếu nó cũng là khoảng trắng thì mình sẽ không xuống dòng nữa (bởi nếu thế thì sẽ bị xuống dòng nhiều lần liên tiếp, không đúng).
• Còn nếu ký tự trước đó khác khoảng trắng (tức là vừa in xong một từ) thì lần này mới xuống dòng.

Thế cho nên trong nhánh else mình thêm điều kiện if(s[i - 1] != ' ') rồi mới cout << endl;:

for(int i = 0; i < length; ++i) { if(s[i] != ' ') cout << s[i]; else { if(s[i - 1] != ' ') cout << endl; } }

Chạy thử với "Nam Son " thì ra kết quả chuẩn hen.

Bước 2: một bug to bự ngay trước mắt – chỉ số âm

Truy xuất s[-1]

Tuy nhiên mình nhìn thấy ngay 1 bug to bự ngay trước mắt: đó là nếu xét đến s[i - 1] mà i duyệt từ 0 trở đi, lỡ với i = 0 mà nó thoả mãn chạy vô cái if(s[i - 1] != ' ') thì $0 - 1 = -1$ là bị âm index, truy xuất vào 1 vị trí không hợp lệ. Bug này sẽ xảy ra khi ký tự đầu tiên của chuỗi là khoảng trắng: nó sẽ thoả cái else và từ đó xét vô cái if bên trong.
Thử với chuỗi " Nam Son " thì may mắn là nó không văng lỗi, nhưng bị lòi ra 1 dòng trống ở đầu. Cái này là may mắn vì trình biên dịch bỏ qua cho lỗi đó, chứ nếu đúng chất thì khi mình gọi s[i - 1] với i đang là 0 thì nó gọi vô s[-1], đáng ra phải bị văng lỗi ngay vì làm gì có index $-1$.

Vậy nên mình phải fix chỗ này. Fix làm sao? ⇒ Mình sẽ cho vòng lặp xét i bắt đầu chạy từ 1, để nếu nó có thoả thì i - 1 cũng chỉ về tới 0, luôn hợp lệ. Mà vòng lặp xét i chạy từ 1 thì mình phải chủ động xét riêng thằng index 0 trước: nếu s[0] khác khoảng trắng thì in nó ra (còn nếu là khoảng trắng thì chắc chắn không cần xuống dòng, vì trước nó chưa có từ nào).

Thuật toán hoàn chỉnh

1. Nếu s[0] != ' ' thì in s[0].
2. Duyệt i từ 1 đến length - 1: nếu s[i] != ' ' thì in s[i]; ngược lại (là khoảng trắng) thì chỉ khi s[i - 1] != ' ' mới xuống dòng.
Mỗi lần xuống dòng xảy ra đúng tại khoảng trắng đầu tiên ngay sau một từ ⇒ không còn dòng trống nào nữa.

Minh hoạ

Em nhập chuỗi (có thể thêm bao nhiêu khoảng trắng tuỳ thích) rồi bấm Tiếp. Ô vàng là ký tự đang xét, ô viền tím nét đứt là ký tự liền trước s[i - 1]:

Chuỗi s

Ví dụ nhanh:

Giờ đây nó đã chính xác hoàn toàn, chuỗi có cỡ nào nó đều đúng. Source code để các bạn tham khảo:

#include <iostream>
#include <string.h>
using namespace std;

int main()
{
    char s[1005];
    cin.getline(s, 1005);
    int length = strlen(s);

    if(s[0] != ' ')
        cout << s[0];

    for(int i = 1; i < length; ++i)
    {
        if(s[i] != ' ')
            cout << s[i];
        else
        {
            if(s[i - 1] != ' ')
                cout << endl;
        }
    }

    return 0;
}

s = input()
length = len(s)

if s[0] != ' ':
    print(s[0], end='')

for i in range(1, length):
    if s[i] != ' ':
        print(s[i], end='')
    else:
        if s[i - 1] != ' ':
            print()

C++▶ Chạy tay từng dòng codeCách 2: xét riêng s[0], rồi i chạy từ 1; gặp khoảng trắng chỉ xuống dòng khi s[i - 1] khác khoảng trắng.

Dữ liệu vào (stdin) – sửa thoải mái Nam Son

Dữ liệu mẫu:

1#include <iostream>

2#include <string.h>

3using namespace std;

4

5int main()

6{

7 char s[1005];

8 cin.getline(s, 1005);

9 int length = strlen(s);

10

11 if(s[0] != ' ')

12 cout << s[0];

13

14 for(int i = 1; i < length; ++i)

15 {

16 if(s[i] != ' ')

17 cout << s[i];

18 else

19 {

20 if(s[i - 1] != ' ')

21 cout << endl;

22 }

23 }

24

25 return 0;

26}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: chỉ cần mảng chứa chuỗi ⇒ $O(N)$.
• Thời gian: duyệt chuỗi đúng một lần, mỗi ký tự làm tối đa 2 phép so sánh ⇒ $O(N)$.

Không gian$O(N)$

Thời gian$O(N)$

Biết thêm cho vui

Trong C++ còn có một cách "lười" là đọc từng từ bằng cin >> w (với string w) trong vòng while, vì cin >> tự bỏ qua mọi khoảng trắng; Python thì có s.split(). Nhưng các bạn mới học nên tự cài đặt theo cách 2 trước để hiểu bản chất duyệt chuỗi và nhất là thói quen soi chỉ số mảng có bị âm / vượt biên không – đây là lỗi rất hay gặp, và nhiều khi chạy trên máy vẫn "may mắn" ra đúng nên càng khó phát hiện.

Ghi chú của mình: code C++ và Python của cách 2 đã được kiểm tra với 500 chuỗi ngẫu nhiên (1 đến 6 từ, khoảng trắng thừa ngẫu nhiên ở đầu, giữa và cuối chuỗi), so với kết quả tách từ chuẩn – khớp hết. Cách 1 sai ở 97/100 chuỗi ngẫu nhiên có khoảng trắng thừa, đúng như phân tích.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇