简历：The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍：Introduction to Algorithms
编程珠玑：Programming Pearls (2nd Edition)
C++ 学习：The C++ Programming Language, 4th Edition
经典操作系统书籍，龙书：Operating System Concepts
创业：The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
Given a string S and a string T, count the number of distinct subsequences of T in S.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,
"ACE" is a subsequence of"ABCDE" while "AEC" is not).
Here is an example:
S =
S =
"rabbbit", T = "rabbit"
Return
» Solve this problem3.I use DP and has the same idea of Palindrome Partitioning. Use a vector to dynamically tracking the number we get.
r a b b b i t
1 1 1 1 1 1 1 1
r 0 1 1 1 1 1 1 1
a 0 0 1 1 1 1 1 1
b 0 0 0 1 2 3 3 3
b 0 0 0 0 1 3 3 3
i 0 0 0 0 0 0 3 3
t 0 0 0 0 0 0 0 3
This table shows clearly of how it algorithm works. We compare from first to end, once we found two chars equal, then we add 1 to result. Because if this two chars equal, it means that we can delete it or keep it.
We may use 2 dimensional vectors to do it, while now we do it in just one 1 dimensional.
Hello, came across your solution while random surfing. It seems that in your second solution, you are looping m*n times to update the record matrix. A lot of those operations will be 0+=0 which seems somewhat unnecessary.
ReplyDeleteI think you can optimize it a bit by scanning T first and create a hash table to track a list of indices for each letter. This way you only need to look up the indices and update accordingly. Same worst case performance(all identical letters), but on average you will get it much faster.
Great Explanation and very neat code .. Thanks
ReplyDelete