leetcode1048最长字符串链

青旅半醒 2023-01-21 03:26 56阅读 0赞

题目：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
解法  
暴力dp\_map比较，例如bdca，拆成bac,bda,bdc，那么count\[bdca\]=max(count\[bca\]+1,count\[bda\]+1,count\[bdc\]+1,count\[dca\]+1)；  
同理  
count\[bca\]=max(count\[bc\]+1,count\[ba\]+1,count\[ca\]+1)；  
count\[bdc\]=max(count\[bc\]+1,count\[bd\]+1,count\[dc\]+1)；  
count\[dca\]=max(count\[dc\]+1,count\[da\]+1,count\[ca\]+1)；  
基础点都是1，是本身，但是如果拆出来的vector< string >里面有的话，那么起码是2  
代码  
dp式子是以短string为基础，所以开始使用排序，先短后长  
map中不存在的话，值为0；

int longestStrChain(vector<string>& words){ 
        sort(words.begin(),words.end(),[](const string &s1,const string &s2){ return s1.size()<s2.size();});
        unordered_map<string,int> u_map;
        for(auto s:words){ 
            u_map[s]=1;
        }
        int max_len = 0;
        for(auto temp:words){ 
            for(int i=0;i<temp.size();i++){ 
                string t = temp.substr(0,i)+temp.substr(i+1);
                u_map[temp] = max(u_map[temp],u_map[t]+1);
            }
            max_len = max(max_len,u_map[temp]);
        }
        return max_len;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20221021/5dc170c2900b49a2928c0d11dc7d372c.png

发表评论取消回复

表情：

评论列表（有 0 条评论，56人围观）

还没有评论，来说两句吧...

相关阅读

相关 leetcode1048最长字符串链

题目： ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmN

青旅半醒/ 2023年01月21日 03:26/ 0 赞/ 57 阅读

相关 LeetCode题目#14（字符串类）——最长公共前缀

原题题目及链接如下： https://leetcode-cn.com/problems/longest-common-prefix/submissions/ ![在这里

青旅半醒/ 2023年01月09日 12:34/ 0 赞/ 131 阅读

相关 LeetCode 14.最长公共前缀（字符串）

上一篇博客：[Leetcode 13.罗马数字转整数（字符串）][Leetcode 13.] > 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepte

素颜马尾好姑娘i/ 2022年11月27日 15:59/ 0 赞/ 133 阅读

相关最长公共字符串

include <iostream> include <string> include <stack> include <algorit

ゞ浴缸里的玫瑰/ 2022年06月17日 04:26/ 0 赞/ 144 阅读

相关 leetcode-14：求字符串数组最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。示例 1: 输入: \["flower","flow","flight"\

超、凢脫俗/ 2022年05月21日 09:22/ 0 赞/ 93 阅读

相关 Java 最长字符串

求出5个字符串中最长的字符串。每个字符串长度在100以内，且全为小写字母。样例输入 one two three four five 样例输出 three 代码：

秒速五厘米/ 2022年04月22日 23:28/ 0 赞/ 159 阅读

相关输出最长字符串

import java.util.Scanner; public class Main \{ public static void main(String\[\] arg

以你之姓@/ 2022年04月10日 02:22/ 0 赞/ 175 阅读

相关【Python】【LeetCode】【5.最长回文字符串】

文章目录 0.回文字符串 1.原文题目 2.解题思路 3.Python代码 0.回

Love The Way You Lie/ 2022年01月29日 23:59/ 0 赞/ 190 阅读

相关 leetcode1048

1 class Solution: 2 def __init__(self): 3 self.dp = {} 4

àì夳堔傛蜴生んèń/ 2021年12月19日 04:13/ 0 赞/ 133 阅读

相关 LeetCode||查找字符串中的最长回文字符串

回文字符串回文字符串就是正着读和反着读都一样的字符串，例如abcdcba 算法--动态规划用一个boolean类型的二维数组T\[i\]\[j\]来表示i到j

系统管理员/ 2021年11月09日 15:28/ 0 赞/ 380 阅读