C/C++教程

【每日一题】【动态规划】2022年1月30日-NC127 最长公共子串

本文主要是介绍【每日一题】【动态规划】2022年1月30日-NC127 最长公共子串，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

描述

给定两个字符串str1和str2,输出两个字符串的最长公共子串 题目保证str1和str2的最长公共子串存在且唯一。

 

方法1：不算动态规划

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        int len1 = str1.length(), len2 = str2.length();
        String[][] dp = new String[len1 + 1][len2 + 1]; //为何初始化为len+1，相当于从1-n
        int max = 0;
        String res = "";
        for(int i = 0; i <= len1; i++) {
            for(int j = 0; j <= len2; j++) {
                if(i == 0 || j == 0) {
                    dp[i][j] = "";
                } else if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + str1.charAt(i - 1);
                    if(dp[i][j].length() > max) {
                        max = dp[i][j].length();
                        res = dp[i][j];
                    }
                } else {
                    dp[i][j] = "";
                }
            }
        }
        return res;
    }
}

类似题目：NC92 最长公共子序列(二)

这篇关于【每日一题】【动态规划】2022年1月30日-NC127 最长公共子串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航