HomeLập trìnhJavaScriptCách giải quyết...

Cách giải quyết thử thách mã hóa Sherlock và Anagrams trong JavaScript


Bài đăng này sẽ giúp bạn tìm ra giải pháp của tôi cho một thử thách mã hóa có tên là “Sherlock và đảo chữ cái”. Bạn có thể xem nó trong HackerRank.

Tôi đã dành rất nhiều thời gian để cố gắng giải quyết nó bằng JavaScript. Khi tôi cố gắng tìm kiếm nó trên google, tôi không thể tìm thấy giải pháp JS phù hợp. Tôi chỉ tìm thấy một và nó không hoạt động chính xác. Ngoài ra, bất kỳ lời giải thích là hoàn toàn ra khỏi câu hỏi. Đó là lý do tại sao tôi quyết định viết một bài báo về nó và cố gắng đưa ra một số giải thích hay và dễ hiểu trong quá trình thực hiện. Tiếp tục đọc ngay bây giờ!

⚠️THẬN TRỌNG: Tôi sẽ đưa ra giải pháp của mình bên dưới với các giải thích ngắn gọn về từng bước. Nếu bạn muốn tự mình thử, vui lòng dừng tại đây và truy cập trang web của HackerRank.

Vấn đề

Hai chuỗi là đảo chữ của nhau nếu các chữ cái của một chuỗi có thể được sắp xếp lại để tạo thành chuỗi kia. Cho một xâu, hãy tìm số cặp xâu con của xâu là đảo chữ của nhau.

Ví dụ s = mẹdanh sách tất cả các cặp đảo ngữ là [m, m], [mo, om] tại các vị trí [[0], [2]], [[0, 1], [1, 2]]tương ứng.

Hạn chế
Độ dài của chuỗi nhập: 2 ≤ |s| ≤ 100
Chuỗi S chỉ chứa các chữ cái viết thường trong phạm vi ascii[a-z].

Phân tích

Điều đầu tiên – chúng ta cần hiểu rõ hơn về toàn bộ vấn đề. Đảo ngữ là gì? một cặp đảo ngữ là gì? Tôi có thể xem một cái không? Ngoài ra, chính xác nó có nghĩa là gì dây phụ?

Nói cách khác, chúng ta cần có một bức tranh rõ ràng về những gì chúng ta đang cố gắng giải quyết, trước khi giải quyết nó.

Từ mô tả của vấn đề, chúng tôi có thể khấu trừ tất cả những gì chúng tôi cần. Tiếp tục đi! ?

Tôi nghĩ đây là thời điểm thích hợp để đề cập rằng thử thách được đề cập nằm trong phần “Từ điển và Hashmap” trên trang web HackerRank. Có lẽ bạn sẽ nghĩ rằng bạn nên sử dụng loại cấu trúc dữ liệu này khi giải nó. ?

phép đảo ngữ

Vì chúng ta sẽ tìm đảo ngữ, hãy bắt đầu với chúng. Như đã mô tả ở trên, đảo chữ của một từ là một từ khác có cùng độ dài và được tạo bằng các ký tự giống nhau từ từ trước đó.

Đọc thêm  JavaScript forEach – Cách lặp qua một mảng trong JS
yqexlCorVcBamgbm1UuU1q2ixW74Zgd50bOs
Hoạt hình cho phép đảo chữ “Nghe = Im lặng”

Vì vậy, chúng ta sẽ phải tìm kiếm các từ và so sánh chúng với các từ khác, để xem chúng có phải là cặp đảo ngữ hay không. Sau khi tìm thấy, chúng tôi sẽ chỉ đếm chúng.

cặp đảo ngữ

Vì chúng ta đã biết đảo chữ là gì, nên tương đối dễ dàng để kết luận rằng một cặp đảo chữ chỉ là hai chuỗi đảo chữ. Chẳng hạn như “mo” và “om”, hoặc “listen” và “im lặng”. Chúng ta sẽ phải đếm có bao nhiêu cặp như thế này có thể được tìm thấy trong một chuỗi nhất định. Để làm được điều đó, chúng ta cần tách chuỗi gốc này thành các chuỗi con.

chuỗi con

Chuỗi con, như tên suy ra, là một phần của chuỗi. Những phần này có thể chỉ là một chữ cái hoặc một cặp chữ cái, chẳng hạn như những gì chúng ta đã thấy trong ví dụ trên —“tôi” hoặc “mo.” Trong giải pháp của chúng tôi, chúng tôi sẽ chia chuỗi gốc thành các chuỗi con như vậy và sau đó chúng tôi sẽ xem xét chúng và thực hiện phép so sánh, điều này sẽ cho chúng tôi biết liệu chúng tôi có các cặp đảo ngữ trong số chúng hay không.

Dung dịch

Bây giờ chúng tôi đã thực hiện phân tích của mình, đã đến lúc chiếu! ?

Hãy tóm tắt:

  1. Chúng ta cần tìm tất cả các chuỗi con của chuỗi đã cho — tạo một phương thức cho điều đó.
  2. Chúng ta cần có khả năng kiểm tra xem hai chuỗi có phải là đảo chữ cái hay không — hãy tạo một phương thức cho điều đó.
  3. Chúng ta cần đếm tất cả các cặp đảo chữ cái trong chuỗi đã cho — hãy tạo một phương thức cho điều đó.
  4. Kết hợp mọi thứ ở trên và đưa ra kết quả — tạo một phương pháp cho điều đó.

Nhận tất cả các chuỗi con

Đây sẽ là phương thức trợ giúp của chúng tôi để tìm tất cả các chuỗi con của một chuỗi đã cho:

function getAllSubstrings(str) {
  let i, j, result = [];

  for (i = 0; i < str.length; i++) {
    for (j = i + 1; j < str.length + 1; j++) {
      result.push(str.slice(i, j))
    }
  }
  return result
}

Như bạn có thể thấy, nó có độ phức tạp thời gian O(n²). Đối với trường hợp của chúng tôi, nó thực hiện công việc vì chúng tôi có độ dài giới hạn của chuỗi đầu vào (tối đa 100 ký tự).

Đọc thêm  Cách nắm bắt tham chiếu so với giá trị trong JavaScript

Kiểm tra đảo chữ

Đây sẽ là phương thức trợ giúp của chúng tôi để kiểm tra xem hai chuỗi có phải là cặp đảo chữ cái hay không:

function isAnagram(str1, str2) {
  const hist = {}

  for (let i = 0; i < str1.length; i++) {
    const char = str1[i]
    if (hist[char]) {
      hist[char]++
    } else {
      hist[char] = 1
    }
  }

  for (let j = 0; j < str2.length; j++) {
    const char = str2[j]
    if (hist[char]) {
      hist[char]--
    } else {
      return false
    }
  }

  return true
}

Hãy nhớ rằng chúng tôi cho rằng rất có thể chúng tôi sẽ phải sử dụng các cấu trúc dữ liệu như hashmap hoặc từ điển (được cung cấp phần thử thách này được tìm thấy trên HackerRank).

Chúng tôi sử dụng một đối tượng JavaScript đơn giản để đóng vai trò của một hashmap. Chúng tôi thực hiện hai lần lặp – một lần trên mỗi chuỗi. Khi chúng tôi lặp lại cái đầu tiên, chúng tôi thêm các ký tự của nó làm khóa cho hashmap và đếm số lần xuất hiện của chúng, chúng sẽ được lưu trữ dưới dạng giá trị của chúng. Sau đó, chúng tôi thực hiện một lần lặp khác trên chuỗi thứ hai. Kiểm tra xem các ký tự của nó có được lưu trữ trong hashmap của chúng tôi không. Nếu có — hãy giảm giá trị của chúng. Nếu thiếu ký tự, có nghĩa là hai chuỗi không phải là một cặp đảo chữ cái, chúng tôi chỉ cần trả về false. Nếu cả hai vòng lặp hoàn thành, chúng tôi trả về true, biểu thị rằng các chuỗi đang được phân tích là một cặp đảo chữ cái.

đếm

Đây là phương pháp mà chúng tôi sẽ sử dụng trình trợ giúp để kiểm tra xem một cặp có đảo ngữ pháp hay không và đếm nó. Chúng tôi làm điều đó với sự trợ giúp của các mảng JavaScript và các phương thức mà chúng cung cấp. Chúng tôi lặp lại một mảng chứa tất cả các chuỗi con của chuỗi ban đầu. Sau đó, chúng tôi lấy đúng phần tử và loại bỏ nó khỏi mảng. Và sau đó chúng tôi thực hiện một vòng lặp khác qua mảng đó và trả về 1 nếu chúng tôi thấy rằng có một đảo chữ cái của phần tử hiện tại. Nếu không tìm thấy gì, chúng tôi trả về 0.

function countAnagrams(currentIndex, arr) {
  const currentElement = arr[currentIndex]
  const arrRest = arr.slice(currentIndex + 1)
  let counter = 0

  for (let i = 0; i < arrRest.length; i++) {
    if (currentElement.length === arrRest[i].length && isAnagram(currentElement, arrRest[i])) {
      counter++
    }
  }

 return counter
}

Và cuối cùng

Điều duy nhất còn lại phải làm bây giờ là kết hợp tất cả những điều trên và nhổ kết quả mong muốn. Đây là cách phương thức cuối cùng trông như thế nào:

function sherlockAndAnagrams(s) {
  const duplicatesCount = s.split('').filter((v, i) => s.indexOf(v) !== i).length

  if (!duplicatesCount) return 0
  let anagramsCount = 0

  const arr = getAllSubstrings(s)

  for (let i = 0; i < arr.length; i++) {
    anagramsCount += countAnagrams(i, arr)
  }

  return anagramsCount
}

Có thể bạn đã nhận thấy, ở đây tôi đang kiểm tra các bản sao trước tiên để biết liệu tôi có nên tiếp tục hay không. Như không có chữ trùng lặp thì không thể có đảo chữ.

Và cuối cùng, chúng tôi đưa tất cả các chuỗi con vào một mảng, lặp lại nó, đếm các cặp đảo ngữ được tìm thấy và trả về số này.

Đọc thêm  Cách viết một lời hứa JavaScript

Bạn có thể tìm thấy mã đầy đủ ở đây.

Phần kết luận

Những loại bài tập này rất tốt để khiến bạn suy nghĩ theo thuật toán. Ngoài ra, họ thay đổi cách làm việc của bạn trong công việc hàng ngày của bạn. Khuyến nghị của tôi là hãy làm điều tương tự mà tôi đang cố gắng làm – thỉnh thoảng rèn luyện trí não của bạn với một trong số đó. Và nếu bạn có thể – hãy chia sẻ. Tôi biết đôi khi bạn không có thời gian cho những thử thách như vậy, nhưng khi bạn có – hãy thực hiện nó.

Cảm giác cá nhân của tôi sau khi hoàn thành việc này là hoàn toàn hài lòng, điều này hoàn toàn dễ hiểu nếu xét về thời gian tôi thực hiện. Nhưng cuối cùng, bạn đọc thân mến, tôi thậm chí còn hạnh phúc hơn khi có thể chia sẻ trải nghiệm này với bạn?!

Cảm ơn vì đã đọc. Đọc thêm các bài viết của tôi tại mihail-gaberov.eu.



Zik.vn – Biên dịch & Biên soạn Lại

spot_img

Create a website from scratch

Just drag and drop elements in a page to get started with Newspaper Theme.

Buy Now ⟶

Bài viết liên quang

DMCA.com Protection Status