Need help with string problem

Revision en1, by qhung312, 2020-06-03 10:31:45

Given a string s and t and a list of transformation arr, determine if after we can turn s into t after applying exactly n transformations from arr (choosing which operation to perform on each turn the string is up to you, as long as it's a valid transformation)

Example: With s = "XO" and t = "XXXO", n = 4 and list of available transformations:

"XX" -> "XO"
"XO" -> "OO"
"O" -> "XX"

Explanation: We can apply the second operation to turn s into "OO". Next apply the third operation to the first character and we'll get "XXO". Apply the third operation to the last character and we get XXXX. Finally, apply the first operation on the last two characters and we get the string s = "XXXO", which is equal to t.


  • The length of s will be no more than 40 characters, and so is t.
  • Length of arr (the list of transformations) is no more than 10.
  • Each string in arr is at maximum 10 characters in length
  • n <= 15
  • Time limit: 1s
Tags #string


  Rev. Lang. By When Δ Comment
en1 English qhung312 2020-06-03 10:31:45 1056 Initial revision (published)