Pattern · Cửa sổ trượtTrung bình
Hoán Vị Trong ChuỗiPermutation in String
Hiểu bài
Cho hai chuỗi s1 và s2. Trả về true nếu bất kỳ hoán vị nào của s1 xuất hiện dưới dạng chuỗi con liên tục trong s2.
Ví dụ:
ts
s1 = "ab", s2 = "eidbaooo"
output = true // "ba" là hoán vị của "ab", xuất hiện tại s2[3..4]
s1 = "ab", s2 = "eidboaoo"
output = false // không có hoán vị nào của "ab" trong s2Hoán vị nghĩa là: cùng bộ ký tự, có thể sắp xếp khác thứ tự.
Bài chỉ xét chữ cái thường a-z.
Cách cơ bản
O(n · m log m) time, O(m) space — n=|s2|, m=|s1|ts
function checkInclusion(s1: string, s2: string): boolean {
// Sinh tất cả hoán vị của s1 → kiểm tra từng cái có trong s2 không
// Với |s1|=10 → 10! = 3.628.800 hoán vị — quá chậm
const sorted1 = s1.split('').sort().join('')
for (let i = 0; i <= s2.length - s1.length; i++) {
const window = s2.slice(i, i + s1.length).split('').sort().join('')
if (window === sorted1) return true
}
return false
}Vì sao cách này chậm:
Mỗi vị trí i phải sắp xếp chuỗi con độ dài m → O(m log m).
- Tổng cộng O(n · m log m).
- Cách này không tận dụng thông tin cửa sổ liền kề.
Mở khoá để xem lời giải tối ưu, chạy thử từng bước và câu hỏi liên quan
Xem đầy đủ chạy thử từng bước, Big-O, trường hợp biên và biến thể công ty Việt Nam.