Chủ đề · 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 {
// The naive idea — generate every permutation of s1 and search for it in s2 —
// is infeasible (|s1|=10 → 10! = 3,628,800). Use this instead: sort each window.
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 và trường hợp biên.