<jupyter_start><jupyter_text>https://leetcode.com/problems/longest-common-subsequence/ https://leetcode.com/problems/longest-common-subsequence/discuss/901695/DFS-greater-DP-Progression-With-Explanation-9010<jupyter_code>from pprint import pprint<jupyter_output><empty_output><jupyter_text>Brute Force<jupyter_code>def longest_sub(seq, sub):
    """
    brute force O(2^N)
    """
    def dfs(seq,sub):
        if not seq or not sub:
            return 0
        if seq[0] == sub[0]:
            return 1 + dfs(seq[1:],sub[1:])
        return max(dfs(seq[1:],sub), dfs(seq,sub[1:]))
    return dfs(seq, sub)
seq = "abcdefgh"
sub = "adhtz"

longest_sub(seq, sub) # 3<jupyter_output><empty_output><jupyter_text>Memoization<jupyter_code>def longest_sub(seq, sub):
    """
    memoization, O(2N)
    i = index for seq
    j = index for sub
    """
    def dfs(dp, i, j):
        if i >= len(seq) or j >= len(sub):
            return 0
        if not dp[i][j]:
            if seq[i] == sub[j]:
                dp[i][j] = 1 + dfs(dp, i+1, j+1)
            else:
                dp[i][j] = max(dfs(dp, i+1, j), dfs(dp, i, j+1))
        return dp[i][j]
    dp = [[None for _ in range(len(sub))] for _ in range(len(seq))]
    return dfs(dp, 0, 0)
seq = "abcdefgh"
sub = "adhtz"

longest_sub(seq, sub) # 3<jupyter_output><empty_output><jupyter_text>Tabulation<jupyter_code>def longest_sub(text1, text2):
    """
    tabulation, O(2N). This is the fastest approach on leetcode.
    """
    l1,l2 = len(text1), len(text2)
    dp = [[0 for _ in range(l2)] for _ in range(l1)]
    
    n = 0
    for i in range(l1):
        if not n and text1[i] == text2[0]: 
            n = 1
        dp[i][0] = n
        
    m = 0
    for j in range(l2):
        if not m and text1[0] == text2[j]:
            m = 1
        dp[0][j] = m
            
    for i in range(1, l1):
        for j in range(1, l2):
            # get the upper left diagnol value and add 1
            if text1[i] == text2[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[l1-1][l2-1]
seq = "abcdefgh"
sub = "abtd"

longest_sub(seq, sub) # 3<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16061705989110708, 'fraction_numerical': 0.03221415607985481, 'mean_word_length': 2.28125, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 19, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '388705', 'license': 'MIT', 'n_tokens_mistral': 918, 'n_tokens_neox': 887, 'n_words': 196, 'path': 'lt1143_longest_sub_sequence_dp.ipynb', 'repo_name': 'devkosal/code_challenges', 'size': '2204'}