Khóa học CTDL và GT

Bài 10.5. Bài tập tổng hợp về xử lý chuỗi

Chào mừng các bạn quay trở lại với chuỗi bài viết về Cấu trúc dữ liệu và Giải thuật! Sau khi đã làm quen với các khái niệm cơ bản và một số kỹ thuật thao tác với chuỗi trong C++, hôm nay chúng ta sẽ cùng nhau tổng hợp và thực hành qua một loạt các bài tập ứng dụng. Xử lý chuỗi là một kỹ năng cực kỳ quan trọng trong lập trình, xuất hiện ở hầu hết mọi lĩnh vực, từ xử lý văn bản, phân tích dữ liệu, xây dựng giao diện, đến phát triển web.

Việc luyện tập với các bài tập đa dạng sẽ giúp chúng ta củng cố kiến thức, làm quen với các hàm và phương thức của lớp std::string trong C++, cũng như rèn luyện tư duy giải quyết vấn đề. Không có cách nào tốt hơn để nắm vững kiến thức ngoài việc bắt tay vào làm bài tập!

Hãy cùng bắt đầu với những thử thách xử lý chuỗi thú vị nhé!

Bài tập 1: Đếm số từ trong một chuỗi

Vấn đề: Cho một chuỗi bất kỳ, hãy đếm xem có bao nhiêu "từ" trong chuỗi đó. Giả định các từ được phân tách bởi một hoặc nhiều ký tự khoảng trắng (' ').

Suy nghĩ: Để đếm số từ, chúng ta có thể duyệt qua chuỗi và nhận diện ranh giới giữa các từ. Một cách phổ biến là đếm số lần chuyển từ ký tự không phải khoảng trắng sang ký tự khoảng trắng, hoặc ngược lại. Một cách tiếp cận khác là đếm số lần chuyển từ ký tự khoảng trắng sang ký tự không phải khoảng trắng (bắt đầu một từ mới), đồng thời xử lý trường hợp chuỗi bắt đầu bằng một từ.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <sstream> // Thư viện để dùng stringstream
#include <algorithm> // Để dùng isspace

int countWords(const std::string& str) {
    if (str.empty()) {
        return 0; // Chuỗi rỗng không có từ nào
    }

    int wordCount = 0;
    bool inWord = false; // Cờ để kiểm tra xem chúng ta có đang ở trong một từ hay không

    // Duyệt qua từng ký tự của chuỗi
    for (char c : str) {
        if (std::isspace(c)) {
            // Nếu gặp khoảng trắng, chúng ta đã ra khỏi một từ (nếu đang ở trong từ)
            inWord = false;
        } else {
            // Nếu gặp ký tự không phải khoảng trắng
            if (!inWord) {
                // Nếu trước đó không ở trong từ, nghĩa là đây là ký tự đầu tiên của một từ mới
                wordCount++;
                inWord = true;
            }
            // Nếu đã ở trong từ rồi thì tiếp tục (không làm gì cả ngoài việc giữ inWord = true)
        }
    }

    return wordCount;
}

int main() {
    std::string s1 = "    Hello world    this is   a test string.   ";
    std::string s2 = "SingleWord";
    std::string s3 = "  Leading and trailing spaces  ";
    std::string s4 = ""; // Chuỗi rỗng
    std::string s5 = "   "; // Chỉ có khoảng trắng

    std::cout << "Chuoi: \"" << s1 << "\" -> So tu: " << countWords(s1) << std::endl;
    std::cout << "Chuoi: \"" << s2 << "\" -> So tu: " << countWords(s2) << std::endl;
    std::cout << "Chuoi: \"" << s3 << "\" -> So tu: " << countWords(s3) << std::endl;
    std::cout << "Chuoi: \"" << s4 << "\" -> So tu: " << countWords(s4) << std::endl;
    std::cout << "Chuoi: \"" << s5 << "\" -> So tu: " << countWords(s5) << std::endl;


    // Minh họa cách dùng stringstream (cách khác, thường đơn giản hơn)
    std::cout << "\n--- Dung stringstream ---" << std::endl;
    std::string s_stream_test = "  Another   test   with stringstream  ";
    std::stringstream ss(s_stream_test);
    std::string word;
    int count_ss = 0;
    while (ss >> word) { // Toán tử >> đọc từng từ (phân tách bởi khoảng trắng)
        count_ss++;
    }
     std::cout << "Chuoi: \"" << s_stream_test << "\" -> So tu: " << count_ss << std::endl;


    return 0;
}

Giải thích code:

1. countWords(const std::string& str): Hàm này nhận vào một chuỗi và trả về số từ.
2. Kiểm tra chuỗi rỗng ban đầu để tránh xử lý không cần thiết.
3. wordCount lưu trữ số từ tìm được.
4. inWord là một cờ Boolean. Nó true khi chúng ta đang "bên trong" một từ (ký tự hiện tại không phải khoảng trắng và ký tự trước đó cũng không phải khoảng trắng, hoặc đây là ký tự không phải khoảng trắng đầu tiên sau một khoảng trắng). Nó false khi chúng ta đang ở vị trí khoảng trắng, hoặc trước khi bắt đầu tìm từ đầu tiên.
5. Chúng ta duyệt qua từng ký tự c trong chuỗi str.
6. Hàm std::isspace(c) (cần <cctype> hoặc <algorithm>) kiểm tra xem ký tự c có phải là khoảng trắng (hoặc các ký tự trống khác như tab, newline) hay không.
7. Nếu c là khoảng trắng, chúng ta chắc chắn không còn ở trong một từ nữa, nên đặt inWord = false.
8. Nếu c không phải là khoảng trắng:
   • Chúng ta kiểm tra cờ inWord. Nếu !inWord đang là true (nghĩa là ký tự trước đó là khoảng trắng hoặc đây là ký tự đầu tiên của chuỗi và nó không phải khoảng trắng), thì đây chính là ký tự bắt đầu một từ mới. Chúng ta tăng wordCount lên 1 và đặt inWord = true để đánh dấu rằng chúng ta đã vào trong một từ.
   • Nếu inWord đã là true, nghĩa là ký tự hiện tại và ký tự trước đó đều không phải khoảng trắng, chúng ta vẫn đang ở trong cùng một từ, không cần làm gì thêm ngoài việc giữ inWord = true.
9. Hàm trả về wordCount.
10. Sử dụng stringstream: Đây là một cách khác và thường đơn giản hơn để xử lý các tác vụ phân tách chuỗi theo khoảng trắng. stringstream coi chuỗi như một luồng (stream). Toán tử >> khi áp dụng cho stringstream sẽ tự động đọc "từng từ" (sequence of non-whitespace characters) và bỏ qua khoảng trắng giữa chúng. Vòng lặp while (ss >> word) sẽ đọc từng từ vào biến word cho đến khi hết chuỗi.

Bài tập 2: Đảo ngược một chuỗi con trong chuỗi

Vấn đề: Cho một chuỗi, cùng với vị trí bắt đầu và kết thúc của một chuỗi con (dựa trên chỉ mục - index, bắt đầu từ 0). Hãy đảo ngược chỉ phần chuỗi con này.

Suy nghĩ: Chúng ta cần truy cập vào phần chuỗi từ chỉ mục start đến chỉ mục end và thực hiện thao tác đảo ngược trên phần đó. Thư viện <algorithm> trong C++ cung cấp hàm std::reverse rất tiện lợi cho việc này, hoạt động trên các iterator.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <algorithm> // Cho std::reverse
#include <vector> // Chỉ dùng cho ví dụ vector để minh họa std::reverse

int main() {
    std::string myString = "abcdefghij";
    int startIndex = 2; // Chỉ mục 'c'
    int endIndex = 6;   // Chỉ mục 'g'

    std::cout << "Chuoi goc: " << myString << std::endl;
    std::cout << "Dao nguoc tu index " << startIndex << " den " << endIndex << std::endl;

    // Kiểm tra chỉ mục hợp lệ
    if (startIndex >= 0 && endIndex < myString.length() && startIndex <= endIndex) {
        // std::string::begin() trả về iterator tới ký tự đầu tiên
        // std::string::begin() + n trả về iterator tới ký tự ở chỉ mục n
        // std::reverse hoạt động trên một phạm vi [first, last), tức là bao gồm first nhưng không bao gồm last.
        // Để đảo ngược từ index start đến end (bao gồm cả end), chúng ta cần phạm vi từ iterator tại start đến iterator tại end + 1.
        std::reverse(myString.begin() + startIndex, myString.begin() + endIndex + 1);

        std::cout << "Chuoi sau khi dao nguoc: " << myString << std::endl;
    } else {
        std::cout << "Chi muc khong hop le!" << std::endl;
    }

    // Minh họa std::reverse với vector để hiểu rõ hơn
    std::cout << "\n--- Minh hoa std::reverse voi vector ---" << std::endl;
    std::vector<int> myVector = {1, 2, 3, 4, 5, 6};
    std::cout << "Vector goc: ";
    for(int x : myVector) std::cout << x << " "; std::cout << std::endl;

    // Dao nguoc toan bo vector
    std::reverse(myVector.begin(), myVector.end());
    std::cout << "Vector sau khi dao nguoc toan bo: ";
    for(int x : myVector) std::cout << x << " "; std::cout << std::endl;

     // Dao nguoc mot phan vector (tu index 1 den 4)
    std::reverse(myVector.begin() + 1, myVector.begin() + 4 + 1); // Pham vi [iterator tai index 1, iterator tai index 5)
    std::cout << "Vector sau khi dao nguoc mot phan (idx 1-4): ";
    for(int x : myVector) std::cout << x << " "; std::cout << std::endl;


    return 0;
}

Giải thích code:

1. Hàm std::reverse từ thư viện <algorithm> nhận hai iterator làm đối số: iterator đầu tiên của phạm vi cần đảo ngược và iterator sau phần tử cuối cùng của phạm vi đó.
2. Trong C++, std::string::begin() trả về một iterator trỏ đến ký tự đầu tiên của chuỗi.
3. Khi bạn cộng một số nguyên n vào std::string::begin(), bạn sẽ nhận được một iterator trỏ đến ký tự ở chỉ mục n.
4. Để đảo ngược chuỗi con từ chỉ mục startIndex đến endIndex (bao gồm cả endIndex), chúng ta cần đảo ngược phạm vi từ iterator tại startIndex (myString.begin() + startIndex) đến iterator sau chỉ mục endIndex (myString.begin() + endIndex + 1). Đây là quy tắc chung của các hàm xử lý phạm vi trong STL (Standard Template Library).
5. Code bao gồm kiểm tra đơn giản xem startIndex và endIndex có nằm trong phạm vi hợp lệ của chuỗi hay không.
6. Phần minh họa với std::vector cho thấy std::reverse hoạt động tương tự trên các container khác của STL, củng cố ý tưởng về làm việc với iterator và phạm vi.

Bài tập 3: Tìm tất cả vị trí xuất hiện của một chuỗi con

Vấn đề: Cho hai chuỗi, chuỗi mẹ (chuỗi lớn) và chuỗi con (chuỗi nhỏ). Hãy tìm và in ra tất cả các chỉ mục (vị trí bắt đầu) mà chuỗi con xuất hiện trong chuỗi mẹ.

Suy nghĩ: Chúng ta có thể sử dụng phương thức string::find của lớp std::string. Phương thức này tìm vị trí đầu tiên của chuỗi con bắt đầu từ một vị trí cụ thể. Chúng ta có thể lặp lại việc gọi find, mỗi lần bắt đầu tìm kiếm sau vị trí tìm thấy trước đó.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <vector> // Để lưu trữ các vị trí tìm thấy

int main() {
    std::string text = "This is a test string. This string contains the word string multiple times.";
    std::string pattern = "string";

    std::cout << "Chuoi me: \"" << text << "\"" << std::endl;
    std::cout << "Chuoi con can tim: \"" << pattern << "\"" << std::endl;

    std::vector<size_t> positions; // Sử dụng size_t cho chỉ mục chuỗi, là kiểu không âm

    size_t pos = text.find(pattern, 0); // Bắt đầu tìm từ chỉ mục 0

    while (pos != std::string::npos) { // std::string::npos là giá trị đặc biệt khi không tìm thấy
        positions.push_back(pos); // Lưu lại vị trí tìm thấy
        // Bắt đầu tìm kiếm cho lần tiếp theo TỪ VỊ TRÍ SAU VỊ TRÍ VỪA TÌM THẤY
        pos = text.find(pattern, pos + pattern.length());
    }

    if (positions.empty()) {
        std::cout << "Chuoi con khong xuat hien trong chuoi me." << std::endl;
    } else {
        std::cout << "Chuoi con xuat hien tai cac vi tri (index): ";
        for (size_t p : positions) {
            std::cout << p << " ";
        }
        std::cout << std::endl;
    }

    return 0;
}

Giải thích code:

1. text.find(pattern, pos) là phương thức tìm kiếm của lớp std::string.
   • Đối số đầu tiên là chuỗi con (pattern) cần tìm.
   • Đối số thứ hai (pos) là chỉ mục bắt đầu tìm kiếm trong chuỗi text. Ban đầu, chúng ta bắt đầu từ 0.
2. text.find trả về chỉ mục đầu tiên mà chuỗi con pattern xuất hiện, bắt đầu từ vị trí pos.
3. Nếu không tìm thấy chuỗi con nào bắt đầu từ vị trí pos, phương thức sẽ trả về một giá trị đặc biệt là std::string::npos.
4. Chúng ta sử dụng một vòng lặp while. Điều kiện lặp là pos != std::string::npos, tức là vòng lặp tiếp tục khi nào vẫn còn tìm thấy chuỗi con.
5. Bên trong vòng lặp:
   • Chúng ta lưu lại vị trí pos vừa tìm thấy vào vector positions.
   • Điều quan trọng là dòng pos = text.find(pattern, pos + pattern.length());. Chúng ta gọi lại find, nhưng lần này bắt đầu tìm kiếm từ vị trí ngay sau kết thúc của chuỗi con vừa tìm thấy (pos + pattern.length()). Điều này đảm bảo chúng ta không tìm lại chính vị trí vừa tìm thấy và tiến về phía trước trong chuỗi mẹ để tìm các lần xuất hiện tiếp theo.
6. Sau khi vòng lặp kết thúc (khi find trả về std::string::npos), vector positions sẽ chứa tất cả các chỉ mục bắt đầu của chuỗi con trong chuỗi mẹ.

Bài tập 4: Kiểm tra chuỗi Palindrome (có phân biệt hoa thường, bỏ qua khoảng trắng)

Vấn đề: Kiểm tra xem một chuỗi có phải là Palindrome hay không, nhưng không phân biệt các ký tự khoảng trắng và có phân biệt chữ hoa chữ thường. Ví dụ: "race car" không phải là palindrome theo tiêu chí này (vì 'r' và 'R' khác nhau), nhưng "taco cat" thì có (sau khi bỏ khoảng trắng là "tacocat").

Suy nghĩ: Để bỏ qua khoảng trắng, chúng ta có thể tạo ra một chuỗi mới chỉ chứa các ký tự không phải khoảng trắng từ chuỗi gốc. Sau đó, chúng ta kiểm tra xem chuỗi mới này có phải là palindrome theo cách thông thường (đọc xuôi và đọc ngược giống nhau) hay không.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <algorithm> // Cho std::isspace
#include <cctype>    // Cho isspace nếu algorithm không đủ

bool isPalindromeIgnoringSpaces(const std::string& str) {
    std::string cleaned_str;
    // Bước 1: Tạo chuỗi mới chỉ chứa các ký tự không phải khoảng trắng
    for (char c : str) {
        if (!std::isspace(c)) {
            cleaned_str += c;
        }
    }

    // Bước 2: Kiểm tra xem chuỗi đã làm sạch có phải là palindrome không
    // Dùng hai con trỏ (chỉ mục), một từ đầu và một từ cuối
    int left = 0;
    int right = cleaned_str.length() - 1;

    while (left < right) {
        // So sánh ký tự ở hai đầu
        if (cleaned_str[left] != cleaned_str[right]) {
            return false; // Nếu khác nhau, không phải palindrome
        }
        // Di chuyển con trỏ vào trong
        left++;
        right--;
    }

    // Nếu vòng lặp kết thúc mà không tìm thấy cặp ký tự khác nhau, thì đó là palindrome
    return true;
}

int main() {
    std::string s1 = "race car";       // -> racecar -> false ('c' != 'C')
    std::string s2 = "A man a plan a canal Panama"; // -> AmanaplanacanalPanama -> false (phân biệt hoa thường)
    std::string s3 = "tacocat";       // -> tacocat -> true
    std::string s4 = " no lemon, no melon "; // -> nolemonnomelon -> true
    std::string s5 = "";               // -> "" -> true (chuỗi rỗng là palindrome)
    std::string s6 = " ";              // -> "" -> true

    std::cout << "\"" << s1 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s1) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << s2 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s2) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << s3 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s3) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << s4 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s4) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << s5 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s5) ? "Yes" : "No") << std::endl;
    std::cout << "\"" << s6 << "\" is palindrome (ignoring spaces)? " << (isPalindromeIgnoringSpaces(s6) ? "Yes" : "No") << std::endl;


    return 0;
}

Giải thích code:

1. Hàm isPalindromeIgnoringSpaces nhận chuỗi gốc str.
2. Tạo một chuỗi mới cleaned_str.
3. Duyệt qua từng ký tự của chuỗi gốc str. Nếu ký tự đó không phải là khoảng trắng (kiểm tra bằng !std::isspace(c)), thêm nó vào cleaned_str.
4. Sau vòng lặp, cleaned_str chỉ còn lại các ký tự không phải khoảng trắng, giữ nguyên thứ tự và phân biệt hoa thường.
5. Tiếp theo, chúng ta sử dụng kỹ thuật hai con trỏ (chỉ mục left và right) để kiểm tra cleaned_str có phải là palindrome hay không.
6. left bắt đầu từ 0 (ký tự đầu tiên), right bắt đầu từ chỉ mục cuối cùng (cleaned_str.length() - 1).
7. Vòng lặp while (left < right) tiếp tục chừng nào hai con trỏ chưa vượt qua nhau.
8. Trong mỗi lần lặp, so sánh ký tự tại cleaned_str[left] và cleaned_str[right].
9. Nếu chúng khác nhau, chuỗi không phải là palindrome, trả về false ngay lập tức.
10. Nếu chúng giống nhau, di chuyển left tiến lên 1 (left++) và right lùi về 1 (right--) để so sánh cặp ký tự tiếp theo.
11. Nếu vòng lặp kết thúc mà không trả về false, nghĩa là tất cả các cặp ký tự đối xứng đều giống nhau, chuỗi là palindrome, trả về true.

Bài tập 5: Chuyển đổi toàn bộ chuỗi sang chữ hoa hoặc chữ thường

Vấn đề: Viết hàm để chuyển đổi tất cả các ký tự chữ cái trong một chuỗi sang chữ hoa hoặc chữ thường tương ứng.

Suy nghĩ: Chúng ta cần duyệt qua từng ký tự trong chuỗi. Đối với mỗi ký tự, kiểm tra xem nó có phải là chữ cái hay không, sau đó sử dụng các hàm chuyển đổi ký tự như tolower hoặc toupper. Thư viện <algorithm> cùng với std::transform là công cụ mạnh mẽ cho phép áp dụng một hàm cho từng phần tử trong một phạm vi.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <algorithm> // Cho std::transform
#include <cctype>    // Cho std::tolower, std::toupper

// Hàm chuyển đổi sang chữ thường
std::string toLower(std::string str) { // Pass by value để tạo bản sao và chỉnh sửa
    std::transform(str.begin(), str.end(), str.begin(),
                   [](unsigned char c){ return std::tolower(c); }); // Sử dụng lambda expression
    return str;
}

// Hàm chuyển đổi sang chữ hoa
std::string toUpper(std::string str) { // Pass by value để tạo bản sao và chỉnh sửa
    std::transform(str.begin(), str.end(), str.begin(),
                   [](unsigned char c){ return std::toupper(c); }); // Sử dụng lambda expression
    return str;
}

int main() {
    std::string mixedCase = "Hello World! 123 ABC";

    std::cout << "Chuoi goc: " << mixedCase << std::endl;
    std::cout << "Chuoi sau khi chuyen sang chu thuong: " << toLower(mixedCase) << std::endl;
    std::cout << "Chuoi sau khi chuyen sang chu hoa: " << toUpper(mixedCase) << std::endl;

    std::string alreadyLower = "all lower case";
    std::string alreadyUpper = "ALL UPPER CASE";

    std::cout << "\nChuoi goc: " << alreadyLower << std::endl;
    std::cout << "Chuoi sau khi chuyen sang chu hoa: " << toUpper(alreadyLower) << std::endl;

     std::cout << "\nChuoi goc: " << alreadyUpper << std::endl;
    std::cout << "Chuoi sau khi chuyen sang chu thuong: " << toLower(alreadyUpper) << std::endl;


    return 0;
}

Giải thích code:

1. Chúng ta sử dụng hàm std::transform từ thư viện <algorithm>. Hàm này nhận 4 đối số:
   • Iterator đầu tiên của phạm vi nguồn (str.begin()).
   • Iterator cuối cùng của phạm vi nguồn (str.end()).
   • Iterator đầu tiên của phạm vi đích (str.begin()). Trong trường hợp này, chúng ta muốn ghi đè kết quả trở lại chính chuỗi gốc, nên phạm vi nguồn và đích là như nhau.
   • Một hàm (hoặc callable object như lambda expression) sẽ được áp dụng cho từng phần tử trong phạm vi nguồn. Kết quả của hàm này sẽ được ghi vào vị trí tương ứng trong phạm vi đích.
2. Lambda expression [](unsigned char c){ return std::tolower(c); } định nghĩa một hàm ẩn danh. Nó nhận một ký tự c (được truyền dưới dạng unsigned char vì các hàm tolower/toupper trong C++ tiêu chuẩn hoạt động trên int và mong đợi giá trị có thể biểu diễn dưới dạng unsigned char hoặc EOF) và trả về kết quả của std::tolower(c). Tương tự với std::toupper.
3. std::tolower(c) chuyển đổi ký tự c sang chữ thường nếu nó là chữ hoa, giữ nguyên nếu không phải chữ cái hoặc đã là chữ thường. std::toupper(c) hoạt động tương tự cho chữ hoa.
4. Hàm toLower và toUpper nhận chuỗi bằng giá trị (std::string str). Điều này tạo ra một bản sao của chuỗi gốc bên trong hàm, cho phép chúng ta chỉnh sửa bản sao đó mà không làm thay đổi chuỗi ban đầu được truyền vào từ main. Sau khi chuyển đổi, bản sao đã chỉnh sửa được trả về. Nếu muốn sửa đổi chuỗi gốc trực tiếp, chúng ta có thể truyền tham chiếu (std::string& str) và bỏ qua việc trả về chuỗi.

Bài tập 6: Xóa bỏ các ký tự trùng lặp liên tiếp

Vấn đề: Cho một chuỗi, hãy tạo một chuỗi mới bằng cách xóa bỏ các ký tự bị lặp lại liên tiếp. Ví dụ: "aaabbbcccdaaa" -> "abcda".

Suy nghĩ: Chúng ta có thể duyệt qua chuỗi gốc và xây dựng chuỗi kết quả. Khi duyệt, chúng ta chỉ thêm ký tự hiện tại vào chuỗi kết quả nếu nó khác với ký tự cuối cùng đã được thêm vào chuỗi kết quả. Cần xử lý trường hợp ký tự đầu tiên.

Code minh hoạ (C++):

#include <iostream>
#include <string>
#include <vector>

std::string removeConsecutiveDuplicates(const std::string& str) {
    if (str.empty()) {
        return ""; // Chuỗi rỗng thì trả về chuỗi rỗng
    }

    std::string result = "";
    result += str[0]; // Luôn thêm ký tự đầu tiên

    // Duyệt từ ký tự thứ hai
    for (size_t i = 1; i < str.length(); ++i) {
        // So sánh ký tự hiện tại với ký tự cuối cùng đã thêm vào chuỗi kết quả
        if (str[i] != result.back()) { // result.back() trả về ký tự cuối cùng của chuỗi result
            result += str[i]; // Nếu khác, thêm ký tự hiện tại vào kết quả
        }
        // Nếu giống, bỏ qua (không thêm)
    }

    return result;
}

int main() {
    std::string s1 = "aaabbbcccdaaa";
    std::string s2 = "foobar"; // Không có ký tự lặp liên tiếp
    std::string s3 = "aaaaa";
    std::string s4 = "";
    std::string s5 = "a";
    std::string s6 = "abbcccddddeeeeffffg";

    std::cout << "\"" << s1 << "\" -> \"" << removeConsecutiveDuplicates(s1) << "\"" << std::endl;
    std::cout << "\"" << s2 << "\" -> \"" << removeConsecutiveDuplicates(s2) << "\"" << std::endl;
    std::cout << "\"" << s3 << "\" -> \"" << removeConsecutiveDuplicates(s3) << "\"" << std::endl;
    std::cout << "\"" << s4 << "\" -> \"" << removeConsecutiveDuplicates(s4) << "\"" << std::endl;
    std::cout << "\"" << s5 << "\" -> \"" << removeConsecutiveDuplicates(s5) << "\"" << std::endl;
    std::cout << "\"" << s6 << "\" -> \"" << removeConsecutiveDuplicates(s6) << "\"" << std::endl;

    return 0;
}

Giải thích code:

1. Hàm removeConsecutiveDuplicates nhận chuỗi gốc str.
2. Xử lý trường hợp chuỗi rỗng.
3. Khởi tạo chuỗi kết quả result. Ký tự đầu tiên của chuỗi gốc (str[0]) luôn được thêm vào result vì nó không thể bị lặp lại liên tiếp với ký tự đứng trước nó (vì không có ký tự nào đứng trước!).
4. Duyệt qua chuỗi gốc str bắt đầu từ chỉ mục 1.
5. Trong mỗi bước lặp, so sánh ký tự hiện tại str[i] với ký tự cuối cùng đã được thêm vào chuỗi result. Phương thức result.back() trả về ký tự cuối cùng của chuỗi result.
6. Nếu str[i] khác với result.back(), nghĩa là ký tự hiện tại không bị trùng lặp liên tiếp với ký tự trước đó (trong chuỗi kết quả), nên chúng ta thêm str[i] vào result.
7. Nếu str[i] giống với result.back(), nó là ký tự lặp lại liên tiếp, chúng ta bỏ qua nó và không thêm vào result.
8. Sau khi duyệt hết chuỗi gốc, result chứa chuỗi đã loại bỏ các ký tự trùng lặp liên tiếp.

Bài tập 7: Thay thế tất cả các ký tự/chuỗi con

Vấn đề: Cho một chuỗi, một chuỗi con cần tìm (find string), và một chuỗi con thay thế (replace string). Hãy thay thế tất cả các lần xuất hiện của chuỗi con cần tìm bằng chuỗi con thay thế trong chuỗi gốc.

Suy nghĩ: Giống như bài tìm tất cả vị trí, chúng ta sẽ sử dụng phương thức string::find để tìm vị trí của chuỗi con cần thay thế. Khi tìm thấy, chúng ta sử dụng phương thức string::replace để thực hiện việc thay thế. Sau đó, chúng ta tiếp tục tìm kiếm từ vị trí sau đoạn vừa thay thế.

Code minh hoạ (C++):

#include <iostream>
#include <string>

void replaceAll(std::string& str, const std::string& from, const std::string& to) {
    if (from.empty()) {
        return; // Không thể thay thế nếu chuỗi cần tìm là rỗng
    }

    size_t start_pos = 0; // Bắt đầu tìm kiếm từ đầu chuỗi
    while ((start_pos = str.find(from, start_pos)) != std::string::npos) {
        // Tìm thấy chuỗi 'from' tại vị trí 'start_pos'

        // Thay thế phần chuỗi từ 'start_pos' với độ dài bằng 'from.length()' bằng chuỗi 'to'
        str.replace(start_pos, from.length(), to);

        // Tiếp tục tìm kiếm từ vị trí SAU đoạn vừa thay thế
        // Điều này quan trọng để tránh lặp vô hạn nếu 'to' chứa 'from'
        // hoặc để xử lý trường hợp chuỗi thay thế 'to' dài hơn 'from'.
        start_pos += to.length();
    }
}

int main() {
    std::string text1 = "This is a test string. string string.";
    std::string find1 = "string";
    std::string replace1 = "text";

    std::cout << "Chuoi goc: \"" << text1 << "\"" << std::endl;
    std::cout << "Thay the tat ca \"" << find1 << "\" bang \"" << replace1 << "\"" << std::endl;
    replaceAll(text1, find1, replace1);
    std::cout << "Chuoi sau khi thay the: \"" << text1 << "\"" << std::endl;

    std::cout << "--------------------" << std::endl;

    std::string text2 = "ababab";
    std::string find2 = "ab";
    std::string replace2 = "abc";

    std::cout << "Chuoi goc: \"" << text2 << "\"" << std::endl;
    std::cout << "Thay the tat ca \"" << find2 << "\" bang \"" << replace2 << "\"" << std::endl;
    replaceAll(text2, find2, replace2);
    std::cout << "Chuoi sau khi thay the: \"" << text2 << "\"" << std::endl;

    std::cout << "--------------------" << std::endl;

    std::string text3 = "aaaaa";
    std::string find3 = "aa";
    std::string replace3 = "a";

    std::cout << "Chuoi goc: \"" << text3 << "\"" << std::endl;
    std::cout << "Thay the tat ca \"" << find3 << "\" bang \"" << replace3 << "\"" << std::endl;
    replaceAll(text3, find3, replace3); // Cẩn thận với trường hợp chồng lấn hoặc thay thế làm xuất hiện lại chuỗi cần tìm
    std::cout << "Chuoi sau khi thay the: \"" << text3 << "\"" << std::endl; // Output có thể là "aaa" hoặc "a" tùy cách xử lý vòng lặp

    // Lưu ý: Cách implement này tìm và thay thế tuần tự, có thể bỏ sót trường hợp
    // như "ababab", thay "ab" bằng "ba" -> "bababa". Thay "ab" đầu tiên -> "babab".
    // Tiếp tục tìm từ sau "ba" (idx 2), tìm thấy "ab" -> "babb".
    // Để xử lý mọi trường hợp chồng lấn phức tạp cần thuật toán khác (như KMP + replace)
    // Tuy nhiên, cách này hoạt động đúng cho đa số trường hợp không chồng lấn phức tạp.

    return 0;
}

Giải thích code:

1. Hàm replaceAll nhận chuỗi cần sửa đổi bằng tham chiếu (std::string& str) để có thể thay đổi trực tiếp chuỗi gốc. Nó cũng nhận chuỗi cần tìm (from) và chuỗi thay thế (to).
2. Kiểm tra trường hợp chuỗi cần tìm (from) rỗng.
3. Biến start_pos lưu trữ vị trí bắt đầu tìm kiếm trong chuỗi str. Ban đầu là 0.
4. Vòng lặp while sử dụng kết quả của str.find(from, start_pos) để kiểm tra.
   • str.find(from, start_pos) tìm vị trí đầu tiên của from trong str, bắt đầu từ chỉ mục start_pos. Kết quả được gán cho start_pos.
   • Vòng lặp tiếp tục chừng nào tìm thấy (start_pos != std::string::npos).
5. Bên trong vòng lặp (khi đã tìm thấy):
   • str.replace(start_pos, from.length(), to) thực hiện việc thay thế. Phương thức replace có nhiều dạng overloaded. Dạng này nhận:
     • Chỉ mục bắt đầu thay thế (start_pos).
     • Số lượng ký tự cần xóa khỏi chuỗi gốc (độ dài của from).
     • Chuỗi sẽ chèn vào vị trí đó (to).
6. Sau khi thay thế, chúng ta cập nhật start_pos để tiếp tục tìm kiếm từ vị trí sau đoạn vừa chèn: start_pos += to.length(). Điều này là cần thiết để tránh tìm lại đoạn vừa thay thế (nếu to chứa from) và đảm bảo chúng ta tiến về phía trước trong chuỗi.

Bài tập ví dụ:

[Xâu kí tự].Ký tự xuất hiện nhiều nhất trong xâu.

Cho một xâu kí tự S, hãy tìm kí tự có số lần xuất hiện nhiều nhất ở trong xâu. Trong trường hợp có nhiều kí tự có cùng số lần xuất hiện lớn nhất thì in ra kí tự có thứ tự từ điển lớn nhất.

Input Format

Xâu kí tự S chỉ bao gồm chữ cái in hoa và in thường và không quá 1000 kí tự.

Constraints

.

Output Format

In ra từ có số lần suất hiện nhiều nhất và số lần xuất hiện tương ứng cách nhau 1 dấu cách.

Ví dụ:

Dữ liệu vào

modmpoemdpeomapoqopekifrmovmxmomsomporfvomtmtb

Dữ liệu ra

m 11

Đây là hướng dẫn giải bài "Ký tự xuất hiện nhiều nhất trong xâu" bằng C++ một cách ngắn gọn:

1. Đếm tần suất: Sử dụng một mảng hoặc map để lưu trữ số lần xuất hiện của mỗi ký tự trong xâu. Có thể dùng mảng int count[256] để tận dụng giá trị ASCII của ký tự làm chỉ số. Duyệt qua xâu đầu vào, với mỗi ký tự, tăng giá trị tương ứng trong mảng/map đếm tần suất.

2. Tìm ký tự có tần suất lớn nhất (và xử lý trường hợp hòa): Duyệt qua mảng/map đếm tần suất. Giữ lại ký tự có tần suất cao nhất và tần suất đó. Trong quá trình duyệt, nếu gặp một ký tự khác có tần suất bằng với tần suất cao nhất hiện tại, so sánh ký tự đó với ký tự đang giữ: nếu ký tự mới có thứ tự từ điển lớn hơn, cập nhật lại ký tự có tần suất cao nhất là ký tự mới này (tần suất giữ nguyên).

3. In kết quả: Sau khi duyệt xong, in ra ký tự tìm được và tần suất tương ứng, cách nhau bởi dấu cách.

Làm thêm nhiều bài tập miễn phí tại đây