leetcode 139单词拆分

简介: leetcode 139单词拆分

单词拆分

a5b6d142b78a404baab063218016d0fb.png

动态规划

单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。
拆分时可以重复使用字典中的单词,说明就是一个完全背包!


dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

dp[0]初始为true完全就是为了推导公式。

下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

1e233e04b60b4d66a438501c16e3c77d.png


dp[j]=true 来自于 dp[i]=true + 字串s(i,j-i)可以在字典中找到。

例如输入“leetcode” ,dp[ 0 ] 初始化为1 ,

dp[ 4 ] = 1 , 因为 dp[ 0 ] =1 ,字串 s( 0 , 4 - 0)即”leet“ 可以在字典找到

dp[ 8 ] = 1 , 因为 dp[ 4 ] =1 ,字串 s( 4 , 8 - 4)即”code“ 可以在字典找到

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        vector<bool> dp(s.size()+1 ,false);
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        dp[0] = true;
        // dp[j]=true 来自于 dp[i]=true + 字串s(i,j-i)可以在字典中找到。
        for(int j = 1 ; j<=s.size() ; j++)//背包尺寸
        {
            for(int i = 0 ; i < j ;i++ )//字串长度
            {
                string word = s.substr( i , j-i );
                if(wordSet.find(word) != wordSet.end() && dp[i]==true )
                    dp[j] = true;
            }  
        }
        // for(auto it:dp) cout<<it<<' ';
        return dp[s.size()];
    }
};

二刷

回溯(超时)

class Solution {
public:
    bool result = false;
    vector<string> path;
    void track_back(string &s, vector<string>& wordDict ,int indnx)
    {
        if(result == true) return;
        if(path.size() != 0)
        {
            string tmp;
            for(int i=0 ; i<path.size();i++)
                tmp += path[i];
            if(tmp.size() > s.size()) return;
            else if(tmp == s) 
            {
                result = true;
                return;
            }
        }
        for(int i=indnx ; i<wordDict.size() ;i++)
        {
            path.push_back(wordDict[i]);
            track_back(s,wordDict,indnx);
            path.pop_back();
        } 
        return;
    }
    bool wordBreak(string s, vector<string>& wordDict) {
        track_back(s,wordDict,0);
        return result;
    }
};

动态规划

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordDict_set(wordDict.begin(),wordDict.end());
        vector<bool> dp(s.size()+1 , false);
        dp[0] = true;
        for(int j=1 ; j<=s.size() ;j++)
        {
            for(int i=0 ; i<j ; i++)
            {
                string tmp = s.substr(i,j-i);
                if(wordDict_set.find(tmp) != wordDict_set.end() && dp[i] == true)
                    dp[j] = true;
            }
        }
        return dp[s.size()];
    }
};
相关文章
|
1月前
|
人工智能 BI
力扣561 数组拆分
力扣561 数组拆分
|
3天前
|
算法
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
【LeetCode刷题】滑动窗口解决问题:串联所有单词的子串(困难)、最小覆盖子串(困难)
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
【经典LeetCode算法题目专栏分类】【第3期】回溯问题系列:单词搜索、N皇后问题、判断有效数独、解数独
|
6天前
|
数据采集 机器学习/深度学习 算法
力扣79题:单词搜索
力扣79题:单词搜索
|
6天前
|
存储 SQL 算法
LeetCode题58: 5种算法实现最后一个单词的长度【python】
LeetCode题58: 5种算法实现最后一个单词的长度【python】
|
6天前
|
存储 算法 数据挖掘
LeetCode 题目 30:串联所有单词的子串【python】
LeetCode 题目 30:串联所有单词的子串【python】
|
11天前
|
算法 Java Go
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 58.最后一个单词的长度(Java/C/Python3/Go实现含注释说明,Easy)
11 0
|
11天前
|
存储 算法 Java
【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)
【经典算法】LeetCode 151. 反转字符串中的单词(Java/C/Python3实现含注释说明,中等)
11 0
|
18天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
23 1
|
18天前
|
存储 C语言 容器
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中)
从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别
26 1