14. Longest Common Prefix
Tags:
Easy
Skills:
Binary Search
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Mục tiêu tìm chuỗi tiền tố chung dài nhất xuất hiện ở đầu của tất cả các chuỗi trong một mảng đầu vào. Nếu không có tiền tố chung nào, kết quả trả về là một empty string
Approach - Horizontal scanning
Time and space complexity
Solution - Horizontal scanning
1function longestCommonPrefix(strs: string[]): string {
2 if(strs.length === 0) return "";
3
4 let prefix = strs[0];
5 for(let i = 1; i < strs.length; i++) {
6 while(strs[i].indexOf(prefix) !== 0) {
7 prefix = prefix.substring(0, prefix.length - 1);
8 if(prefix === "") return "";
9 }
10 }
11
12 return prefix;
13};Solution - Binary Search - Optimized for large input
| Binary Search | Divide and Conquer |
| - Thời gian: O(N⋅logM), với N là số chuỗi và M là độ dài chuỗi ngắn nhất.- Chỉ cần kiểm tra một số lượng nhỏ các độ dài (logarithmic steps). | - Thời gian: O(N⋅M), trong đó N là số chuỗi và M là độ dài trung bình của chuỗi.- Mỗi bước chia nhỏ cần so sánh toàn bộ các chuỗi trong nửa tương ứng. |
1function longestCommonPrefix(strs: string[]): string {
2 if (strs.length === 0) return '';
3 let min_len = Math.min(...strs.map(s => s.length));
4
5 let left = 0;
6 let right = min_len;
7 while (left <= right) {
8 const mid = left + Math.floor((right - left) / 2);
9 let prefix = strs[0].substring(0, mid);
10 if (strs.every(s => s.startsWith(prefix))) {
11 left = mid + 1
12 } else {
13 right = mid - 1
14 }
15 }
16 return strs[0].substring(0, left - 1);
17};