diff options
Diffstat (limited to 'other/longest_common_subseq.rs')
-rw-r--r-- | other/longest_common_subseq.rs | 23 |
1 files changed, 23 insertions, 0 deletions
diff --git a/other/longest_common_subseq.rs b/other/longest_common_subseq.rs new file mode 100644 index 0000000..212070a --- /dev/null +++ b/other/longest_common_subseq.rs @@ -0,0 +1,23 @@ +struct Solution; + +impl Solution { + pub fn longest_common_subsequence(text1: String, text2: String) -> i32 { + let mut dp: Vec<Vec<usize>> = vec![vec![0; text2.len() + 1]; text1.len() + 1]; + for (i, c1) in text1.chars().enumerate() { + for (j, c2) in text2.chars().enumerate() { + dp[i + 1][j + 1] = if c1 == c2 { + dp[i][j] + 1 + } else { + std::cmp::max(dp[i][j + 1], dp[i + 1][j]) + } + } + } + dp[text1.len()][text2.len()] as i32 + } +} + +fn main() { + let text1 = String::from("abcde"); + let text2 = String::from("ace"); + print!("{}", Solution::longest_common_subsequence(text1, text2)); //3 +} |