题解 | #最长公共子串#

最长公共子串

http://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac

尽可能地优雅!

class Solution {
public:
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    string LCS(string str1, string str2) {
        // write code here
        int len1 = str1.size(), len2 = str2.size();
        int dp[len1+1][len2+1], max = 0, tagi = 0;
        for(int i = 0; i < len1 + 1; i++) dp[i][0] = 0;
        for(int j = 0; j < len2 + 1; j++) dp[0][j] = 0;
        for(int i = 1; i <= len1; i++){
            for(int j = 1; j <= len2; j++){
                if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = 0;
                if(max < dp[i][j]){
                    max = dp[i][j];
                    tagi = i;
                }
            }
        }
        string ans(str1.begin() + tagi - max, str1.begin() + tagi);
        return ans;
    }
};
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-01 11:27
点赞 评论 收藏
分享
Rena1ssanc...:对的,要是面评没太烂,勤更新简历等捞就行了,腾讯可以无限复活
点赞 评论 收藏
分享
07-03 11:02
中山大学 C++
字节刚oc,但距离九月秋招很近了有两段互联网实习,非腾讯字节。不敢赌转正,现在在纠结去还是不去如果实习俩月离职会有什么后果吗
阿城我会做到的:不去后悔一辈子,能否转正取决于ld的态度,只要他不卡,答辩就是走流程,个人觉得可以冲一把
投递字节跳动等公司9个岗位
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务