angry_pikachu's blog

How to solve this question?
By angry_pikachu, history, 2 years ago, In English

Source — Link

Given a string with lowercase letters and “?” where each “?” can be replaced by any lowercase character, find the total number of strings such that the first and last characters are the same and no adjacent characters are the same.

I am still new to DP, help would be appreciated

  • Vote: I like it
  • +6
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

You can iterate over every possible first character and calculate dp[i][j] — answer for prefix of length i with last character being j. It’s easy to get that dp[i][j] = sum of all dp[i — 1[k] for k != j. If you have s[i] = ‘?’, you calculate dp[i][j] for all j’s, otherwise only for j = s[i]. If you need to speed up your calculation time, you can notice that dp[i][j] = sum[i — 1] — dp[i — 1][j], where sum[i] is sum of dp[i][j] for all j’s. With all of that, you will get solution that works in O(n*26^2)

→ Reply