aboutsummaryrefslogtreecommitdiff
path: root/longest_common_subseq.rs
blob: 212070a09cfe34ffff8890a83f379248c223b032 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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
}