Backtracking #3: number Of Distinct String

Cho xâu s và ký tự c. Tại mỗi vị trí của s bạn có thể chèn ký tự c vào đúng một lần hoặc không chèn. Hãy xác định số xâu khác nhau được tạo từ xâu s và ký tự c.

Ví dụ

• Cho s = 'AB', c = 'C', output là numberOfDistinctString(s, c) = 8.
  Từ s và c có thể tạo ra 8 xâu khác nhau:
  • "AB"
  • "CAB"
  • "ACB"
  • "ABC"
  • "CACB"
  • "ACBC"
  • "CABC"
  • "CACBC"
• Cho s = "AA", c = 'A', output là numberOfDistinctString(s, c) = 4.
  Từ s và c có thể tạo ra 4 xâu khác nhau:
  • "AA"
  • "AAA"
  • "AAAA"
  • "AAAAA"

Đầu vào/Đầu ra

• [Giới hạn thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go

• [Đầu vào] String s
  1 <= s.size <= 10.

• [Đầu vào] String c.
  c.size = 1

• [Đầu ra] Integer
  Số xâu khác nhau được tạo ra từ xâu s và ký tự c.