wordMatch2

Cho một mảng arr gồm các chuỗi và một chuỗi s. Hãy cho biết với những chuỗi có trong arr có bao nhiêu cách tạo ra chuỗi s  bằng cách nối các chuỗi lại (có thể được sử dụng lại những chuỗi đã dùng). Hai cách được gọi là khác nhau nếu danh sách các chuỗi dùng để nối theo thứ tự khác nhau.

Ví dụ:

• Với arr = ["cat", "cats", "and", "sand", "dog"], s= "catsanddog". Đầu ra wordMatch2(arr,s) = 2.

     Giải thích: Ta có thể nối như sau:

         – cat-sand-dog

         – cats-and-dog

• Với arr = ["learn","code","io"], s = "codlearn". Đầu ra wordMatch(arr,s) = 0.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
• [Đầu vào] array of string arr, string s.
  1 ≤ arr.size ≤ 50

        0 <= s.length <= 500.

• [Đầu ra] integer
  Số cách tạo chuỗi s từ mảng arr