[C++] Kỹ thuật xử lý tách chữ số từ xâu

by | Mar 17, 2025 | C/C++, Cấu trúc dữ liệu và giải thuật, Kỹ thuật lập trình, Ngôn ngữ lập trình | 0 comments

Xử lý tách chữ số từ xâu là một kỹ thuật cần biết trong để xử lý chữ số xuất hiện các xâu, kỹ thuật này cần thiết trong các bài toán xử lý chuỗi, trích xuất thông tin số học, và tiền xử lý dữ liệu. Trong bài viết này, chúng ta sẽ xem xét ba cách phổ biến để xử lý tách chữ số từ một xâu bất kỳ.

1. Kỹ thuật chung

Để xử lý tách chữ số từ một xâu trong C++, chúng ta dựa trên các ý tưởng cơ sở sau:

  • Dùng bảng mã ASCII để kiểm tra xem một ký tự có phải là chữ số hay không ('0' <= c && c <= '9').
  • Ghép các chữ số thành một số duy nhất hoặc nhóm các số liên tiếp vào một danh sách.
  • Sử dụng các cấu trúc dữ liệu như string và vector<int> để lưu trữ kết quả.
  • Xử lý theo yêu cầu cụ thể bằng cách thay đổi cách ghép hoặc tách số.

2. Phân tích dựa trên ví dụ

2.1. Ghép tất cả các chữ số từ xâu thành một giá trị duy nhất

Input: Chuỗi S.
Output: Số nguyên là kết quả ghép tất cả các chữ số trong S.

  1. Khởi tạo biến result = 0.
  2. Duyệt từng ký tự c trong S (theo thứ tự trái → phải):
    • Nếu c nằm trong ['0'..'9']:
      • Chuyển c sang giá trị số: digit = c - '0' (từ 0 tới 9).
      • Cập nhật result = result * 10 + digit để “đẩy” các chữ số cũ sang trái một hàng và thêm chữ số mới vào cuối.
    • Nếu c không phải chữ số: bỏ qua.
  3. Kết thúc duyệt, trả về result.

Độ phức tạp:

  • Thời gian: O(n) với n là độ dài chuỗi (mỗi ký tự xử lý 1 lần).
  • Bộ nhớ phụ: O(1).

Minh họa:

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

int extractNumber(const string& S) {
    int result = 0;
    for (char c : S) {
        if ('0' <= c && c <= '9') {
            result = result*10 + (c-'0');
        }
    }
    return result;
}

int main() {
    string S = "ab123abc2";
    cout << "So ghep duoc: " << extractNumber(S) << endl;
    return 0;
}

2.2. Tách các số từ xâu với mỗi số là dãy ký số liên tiếp

Ý tưởng: Duyệt chuỗi trái→phải, tích lũy chữ số liên tiếp vào một biến số nguyên; khi gặp ký tự không phải chữ số thì “chốt” số đang tích lũy và bắt đầu phiên tích lũy mới.

Input: Chuỗi S.
Output: Danh sách (vector) các số nguyên tách được từ chuỗi.

Biến dùng:

  • vector<int> nums – danh sách kết quả.
  • int num = 0 – số đang tích lũy.
  • bool inNumber = false – cờ cho biết có đang ở trong “vùng chữ số” không.

Xử lý:

Duyệt từng ký tự c trong S:

  • Nếu c là chữ số ('0' <= c <= '9'):
    → Cập nhật num = num * 10 + (c - '0').
    → Đặt inNumber = true.
  • Nếu c không phải chữ số và inNumber == true:
    → Đưa số num vào vector nums.
    → Reset num = 0, inNumber = false.
  • Nếu c không phải chữ số và inNumber == false:
    → Bỏ qua.

Sau vòng lặp, nếu inNumber == true (tức chuỗi kết thúc bằng chữ số):
→ Đưa num vào vector nums.

Trả về vector nums.

Ví dụ:

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> extractNumbers(const string& S) {
    vector<int> nums;
    int num = 0;         // Biến tích lũy số hiện tại
    bool inNumber = false; // Cờ đánh dấu đang ở trong một chuỗi số

    for (char c : S) {
        if ('0' <= c && c <= '9') {
            // Nếu là chữ số, tích lũy vào num
            num = num * 10 + (c - '0');
            inNumber = true;
        } else {
            // Nếu gặp ký tự không phải số và đang tích lũy số
            if (inNumber) {
                nums.push_back(num); // Lưu số vừa hoàn thành
                num = 0;             // Reset lại num
                inNumber = false;    // Reset trạng thái
            }
        }
    }

    // Sau vòng lặp, nếu kết thúc bằng một số thì phải lưu nốt
    if (inNumber) nums.push_back(num);

    return nums;
}

int main() {
    string S = "ab123abc2";
    vector<int> nums = extractNumbers(S);

    cout << "Cac so tach duoc: ";
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

2.3. Tách tất cả các số có thể tạo thành từ dãy ký số liên tiếp

Input: Chuỗi sss.
Output: Danh sách (vector) các “số con” duy nhất sinh ra từ mọi đoạn chữ số liên tiếp trong sss, liệt kê theo độ dài tăng dần trong từng đoạn.

Khởi tạo một vector rỗng nums để chứa kết quả.
Khởi tạo một tập seen (hash set) để loại bỏ trùng lặp số con.
Duyệt chỉ số i từ 0 đến s.size()-1:

  • Nếu s[i] là chữ số:
    → Xác định đoạn số liên tiếp bắt đầu tại i: đặt j = i và tăng j cho đến khi j == n hoặc s[j] không phải chữ số. Khi đó, đoạn là s[i..j-1] có độ dài L = j - i.
    → Sinh tất cả số con của đoạn theo độ dài tăng dần:
      Với len từ 1 đến L:
       Khởi tạo val = 0.
       Với mỗi vị trí bắt đầu p từ i đến i + L - len:
        Cập nhật val theo chuỗi con s[p..p+len-1] bằng tích lũy: đặt val = 0, rồi với q từ p đến p+len-1, mỗi bước val = val*10 + (s[q]-'0').
        Nếu val chưa có trong seen, thêm val vào seen và đẩy vào nums.
    → Gán i = j để tiếp tục duyệt sau đoạn số.
  • Nếu s[i] không phải chữ số: tăng i lên 1.

Trả về nums.

Minh họa:

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
using namespace std;

vector<int> extractUniqueSubNumbers(const string& s) {
    vector<int> nums;
    unordered_set<int> seen;
    int n = s.size();

    for (int i = 0; i < n; ) {
        if ('0' <= s[i] && s[i] <= '9') {
            int j = i;
            while (j < n && '0' <= s[j] && s[j] <= '9') j++;
            // đoạn số liên tiếp là s[i..j-1]
            int L = j - i;

            // sinh tất cả số con theo độ dài tăng dần
            for (int len = 1; len <= L; ++len) {
                for (int p = i; p + len - 1 < j; ++p) {
                    int val = 0;
                    for (int q = p; q < p + len; ++q) {
                        val = val * 10 + (s[q] - '0');
                    }
                    if (seen.find(val) == seen.end()) {
                        seen.insert(val);
                        nums.push_back(val);
                    }
                }
            }
            i = j; // nhảy qua đoạn số
        } else {
            i++;
        }
    }
    return nums;
}

int main() {
    string s = "ab123abc2";
    vector<int> nums = extractUniqueSubNumbers(s);

    cout << "Output: [";
    for (int i = 0; i < (int)nums.size(); i++) {
        cout << nums[i];
        if (i + 1 < (int)nums.size()) cout << ",";
    }
    cout << "]\n";
    return 0;
}

Kết luận

Trong bài viết này, chúng ta đã tìm hiểu ba ví dụ khác nhau để trích xuất số từ xâu :

  1. Ghép tất cả chữ số thành một số duy nhất
  2. Tách các dãy chữ số liên tiếp thành một danh sách
  3. Tạo tất cả các số con có thể từ dãy chữ số liên tiếp

Hy vọng thông qua ba ví dụ này, bạn có thể tự xây dựng cho mình các phương thức khác để giải quyết các yêu cầu trong quá trình giải các bài toán liên quan.