Problem #5: Shortest substring containing all the characters in the set

Status: RESOLVED
Cho một string có nội dung "figehaeci" và một set các kí tự {a, e, i}, tìm ra một substring ngắn nhất chứa tất cả các kí tự trong set. Trong trường hợp trên kết quả đúng trả về là "aeci"

Nếu như không có substring nào chứa tất cả các kí tự thì return về null]

Noted: Không quan tâm thứ của substring và set các kí tự trả về, ví dụ:

"figehaeci" => "aeci"
"figehacei" => "acei"

.......

🎄🎁🎄🎁🎄🎁🎄🎁🎄

Các bạn có câu hỏi nào thì để ở phần bình luận nha.

Bài viết đã được updated lời giải, tuy nhiên khoan hãy scroll xuống đọc tiếp. Các bạn hãy suy nghĩ giải trước nha ???

Code thôi ??? !!!

Mình tiếp cận bằng cách duyệt qua strings này nếu gặp một kí tự nằm trong set thì mình sẽ duyệt từ vị trí này để tìm cho đến khi gặp được một chuỗi chứa tất cả các kí tự trong set:

Hàm findSubstring:

Mỗi lần duyệt mình sẽ lấy ra được một chuỗi thoả, so sánh length với kết quả trước đó để tìm ra được substring nhỏ nhất thoả.

Cách này có thể thoả yêu cầu bài toán, nhưng theo mình nghĩ nó vẫn chưa phải là tối ưu. Vì mình phải tốn một lần duyệt mảng và lỗi lần tìm được kí tự đầu tiên thoả mình vẫn phải duyệt một lần nữa để tìm kết quả đúng.

Mình vẫn đang thử tiếp cận một cách khác xem có cách nào tối ưu hơn không.

  • dailycoding
  • algorithm
  • programming
Loading
Đăng nhập để bình luận