Toán tin vuotlen.com

14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

Constraints:

 

// Horizontal Scanning (Quét ngang)

// lấy cái đầu tiên rồi so sánh, strs[i].find(prefix)  !=0

// strs[i].compare(0, prefix.size(), prefix) != 0 để quét đầu chuỗi thay vì find quét toàn bộ chuỗi

 

class Solution {

public:

    string longestCommonPrefix(vector<string>& strs) {

        if (strs.empty()) return "";

        string prefix = strs[0];

        for (int i=1; i< strs.size();i++){

            while(strs[i].compare(0, prefix.size(), prefix) != 0){

                prefix = prefix.substr(0, prefix.size()-1);

                if (prefix.empty()) return "";

            }

        }

        return prefix;

    }

};

 

Dữ liệu đầu vào: strs = ["flower", "flow", "flight"]

Bước 1: Khởi tạo

Bước 2: Vòng lặp for lần 1 (i = 1)

Bước 3: Vòng lặp for lần 2 (i = 2)

Bước 4: Kết thúc

Phân tích nhanh về hàm compare

Trong đoạn code này, strs[i].compare(0, prefix.size(), prefix) cực kỳ an toàn vì:

  1. Tham số 1 (0): Bắt đầu so sánh từ vị trí đầu tiên của strs[i].

  2. Tham số 2 (prefix.size()): Chỉ so sánh một đoạn có độ dài bằng đúng prefix.

  3. Tham số 3 (prefix): Chuỗi mẫu để so sánh.

Lưu ý: Nếu prefix.size() lớn hơn độ dài của strs[i], hàm compare vẫn hoạt động bình thường và trả về giá trị khác 0, giúp vòng lặp while tiếp tục cắt ngắn prefix cho đến khi nó vừa khớp.

 

//Vertical Scanning (Quét dọc)

// so sánh ký tự thứ nhất của tất cả các chuỗi, rồi đến ký tự thứ hai...

class Solution {

public:

    string longestCommonPrefix(vector<string>& strs) {

        if (strs.empty()) return "";

       

        for (int i = 0; i < strs[0].length(); i++) {

            char c = strs[0][i];

            for (int j = 1; j < strs.size(); j++) {

                // Nếu đi hết chiều dài của một chuỗi hoặc ký tự không khớp

                if (i == strs[j].length() || strs[j][i] != c) {

                    return strs[0].substr(0, i);

                }

            }

        }

        return strs[0];

    }

};

 

Chạy từng dòng code (Dry Run):

Khởi tạo: strs = ["flower", "flow", "flight"]

Vòng lặp 1: Xét cột i = 0

Vòng lặp 2: Xét cột i = 1

Vòng lặp 3: Xét cột i = 2

Kết quả cuối cùng: "fl"

 

 

1. Tại sao phải kiểm tra i == strs[j].length()?

Trong vòng lặp, biến i đại diện cho chỉ số ký tự hiện tại mà chúng ta đang xét. Nếu i đã bằng với độ dài của một chuỗi nào đó trong mảng, điều đó có nghĩa là chúng ta đã duyệt hết sạch ký tự của chuỗi ngắn nhất đó rồi.

2. Ví dụ minh họa

Giả sử bạn có: strs = ["flow", "f"]

Bước 1: Xét cột i = 0

Bước 2: Xét cột i = 1

3. Thứ tự của điều kiện (Short-circuit evaluation)

Trong C++, toán tử || (OR) hoạt động theo cơ chế ngắt mạch:

Tóm lại:

Chỉ cần một trong hai điều kiện này đúng, nghĩa là tiền tố chung đã kết thúc tại vị trí i.

 

 

// Sắp xếp (Sorting)

// so sánh chuỗi đầu tiên và chuỗi cuối cùng

class Solution {

public:

    string longestCommonPrefix(vector<string>& strs) {

        if (strs.empty()) return "";

       

        // 1. Sắp xếp mảng theo thứ tự từ điển

        sort(strs.begin(), strs.end());

       

        string first = strs[0];

        string last = strs.back();

        string result = "";

       

        // 2. Chỉ cần so sánh chuỗi đầu và chuỗi cuối

        for (int i = 0; i < min(first.size(), last.size()); i++) {

            if (first[i] != last[i]) {

                return result;

            }

            result += first[i];

        }

       

        return result;

    }

};

 

Các bước thực thi:

1. Khởi tạo:

2. Sắp xếp mảng (sort(strs.begin(), strs.end())):

3. Xác định first và last:

4. Vòng lặp so sánh first và last:

Ta sẽ so sánh từng ký tự tại chỉ số $i$:

Kết quả cuối cùng: "fl"