Đề bài
A subsequence is formed by deleting zero or more elements while preserving the order of the remaining elements. Find the longest length shared by two arrays. Matching elements need not be adjacent. Return only the length, since several equally long subsequences may exist.
Implement longest_common_subsequence_length(first, second).
Input
first: The first sequence.
second: The second sequence.
Output
Return the maximum common subsequence length. If either array is empty, return 0.
Ràng buộc
Each array has 0…1,000 integers between −1,000,000,000 and 1,000,000,000. Duplicates are allowed.
Ví dụ
Đầu vào:
first = [1, 3, 2, 4]
second = [3, 1, 2, 4]
Kết quả mong đợi:
expected = 3Đầu vào:
std::vector<long long> first = {1, 3, 2, 4};
std::vector<long long> second = {3, 1, 2, 4};
Kết quả mong đợi:
long long expected = 3;Đầu vào:
long[] first = new long[] {1, 3, 2, 4};
long[] second = new long[] {3, 1, 2, 4};
Kết quả mong đợi:
long expected = 3;Giải thích
Both contain [1, 2, 4] in that order, after deleting one value. The original arrays differ, so a length-four match is impossible.
Đầu vào:
first = [1, 2]
second = [3, 4]
Kết quả mong đợi:
expected = 0Đầu vào:
std::vector<long long> first = {1, 2};
std::vector<long long> second = {3, 4};
Kết quả mong đợi:
long long expected = 0;Đầu vào:
long[] first = new long[] {1, 2};
long[] second = new long[] {3, 4};
Kết quả mong đợi:
long expected = 0;Giải thích
The arrays have no shared value, so their only common subsequence is empty.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Bạn đang khớp thứ tự, không phải kề nhau, nên các lựa chọn bỏ qua quan trọng hơn việc canh thẳng trực tiếp.
Gợi ý 2
Dùng dynamic programming với mỗi trạng thái so sánh các tiền tố của hai mảng.
Gợi ý 3
Khi phần tử khác nhau, lấy kết quả tốt hơn từ việc bỏ một phần tử ở một trong hai dãy; các giá trị lặp có thể tạo nhiều cách khớp hợp lệ.
Độ phức tạp mong đợi
thời gian O(nm), bộ nhớ phụ O(min(n, m))
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.