aboutsummaryrefslogtreecommitdiff
path: root/other/longest_common_subseq.rs
diff options
context:
space:
mode:
Diffstat (limited to 'other/longest_common_subseq.rs')
-rw-r--r--other/longest_common_subseq.rs23
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
+}