[DAY26]Abbreviation
1 min readDec 2, 2019
Solution: Dynamic Programming.
We must divide this problem into small subproblems. First, by observing the characters in the string b. We would notice that if a character in string b is also in string a. Then we would check the value of dp[row-1][col-1] to make sure the substring before the character in the string b also meets the requirement. Else, if the lower case of the character in the string b exists in the string a, we can choose to uppercase the character or simply delete this character. Hence we run an or operation on the value of dp[row-1][col-1] and dp[row][col-1]. Last, if the character in the string b is in lowercase, we can simply delete it. So we assign the value of dp[row][col-1] to it.