Bài 14 Leetcode: Longest Common Prefix

Đề bài:

Viết một hàm để tìm chuỗi tiền tố chung dài nhất giữa một mảng các chuỗi. Nếu không có chuỗi tiền tố chung, trả về một chuỗi rỗng “”.

Ví dụ 1:

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

Ví dụ 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Giải thích: Không có chuỗi tiền tố chung giữa các chuỗi đầu vào.

Ràng buộc:

• 1 <= độ dài của strs <= 200
• 0 <= độ dài của strs[i] <= 200
• strs[i] chỉ bao gồm các chữ cái tiếng Anh viết thường.

Giải thích thuật toán bằng C++

class Solution {
 public:
  string longestCommonPrefix(vector<string>& strs) {
    if (strs.empty())
      return "";

    for (int i = 0; i < strs[0].length(); ++i)
      for (int j = 1; j < strs.size(); ++j)
        if (i == strs[j].length() || strs[j][i] != strs[0][i])
          return strs[0].substr(0, i);

    return strs[0];
  }
};

Đây là một đoạn mã trong ngôn ngữ C++ để triển khai hàm longestCommonPrefix(vector<string>& strs) theo thuật toán đã mô tả trước đó. Dưới đây là giải thích chi tiết về thuật toán này:

1. Hàm longestCommonPrefix(vector<string>& strs): Đây là hàm chính để tìm chuỗi tiền tố chung dài nhất giữa một mảng các chuỗi. Hàm này nhận đầu vào là một vector strs chứa các chuỗi.

2. Kiểm tra nếu vector strs rỗng, tức là không có chuỗi đầu vào, ta trả về một chuỗi rỗng “”.

3. Sử dụng hai vòng lặp for để duyệt qua các ký tự trong chuỗi đầu tiên của vector strs (strs[0]) từ đầu đến hết:

– Vòng lặp ngoài (i) duyệt qua các ký tự trong chuỗi đầu tiên.

– Vòng lặp trong (j) duyệt qua các chuỗi còn lại trong vector strs.

4. Trong vòng lặp trong, ta kiểm tra các trường hợp sau:

– Nếu i bằng độ dài của chuỗi strs[j] hoặc ký tự thứ i trong chuỗi strs[j] khác với ký tự thứ i trong chuỗi đầu tiên (strs[0]), ta trả về một chuỗi con của strs[0] từ vị trí 0 đến i-1. Đây chính là chuỗi tiền tố chung dài nhất.

– Nếu không có trường hợp trên xảy ra, tiếp tục kiểm tra với các ký tự tiếp theo trong chuỗi đầu tiên.

5. Nếu không có trường hợp trả về trong vòng lặp, tức là tất cả các chuỗi trong vector strs giống nhau, ta trả về chuỗi đầu tiên (strs[0]) là chuỗi tiền tố chung dài nhất.

Thuật toán này sử dụng cách tiếp cận so sánh các ký tự của các chuỗi trong vector strs từ đầu đến hết. Bằng cách so sánh ký tự thứ i của mỗi chuỗi với ký tự thứ i của chuỗi đầu tiên, ta tìm được chuỗi tiền tố chung dài nhất. Nếu có bất kỳ chuỗi nào không khớp hoặc đạt tới cuối chuỗi, ta trả về chuỗi con của chuỗi đầu tiên cho đến ký tự trước đó, đó chính là chuỗi tiền tố chung dài nhất.

Giải thích thuật toán bằng Java

class Solution {
  public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0)
      return "";

    for (int i = 0; i < strs[0].length(); ++i)
      for (int j = 1; j < strs.length; ++j)
        if (i == strs[j].length() || strs[j].charAt(i) != strs[0].charAt(i))
          return strs[0].substring(0, i);

    return strs[0];
  }
}

Giải thích thuật toán bằng Python

class Solution:
  def longestCommonPrefix(self, strs: List[str]) -> str:
    if not strs:
      return ''

    for i in range(len(strs[0])):
      for j in range(1, len(strs)):
        if i == len(strs[j]) or strs[j][i] != strs[0][i]:
          return strs[0][:i]

    return strs[0]