Leetcode: Word Break

小咪咪 2022-08-05 13:07 135阅读 0赞

题目：  
Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given  
s = “leetcode”,  
dict = \[“leet”, “code”\].

Return true because “leetcode” can be segmented as “leet code”.

思路分析：  
按照官方的解法：动态规划（[Dynamic Programming][]）  
感觉自己对动态规划问题还是不能熟练应对。不能准确找出变量之间的递推关系。  
设F(0, i)表示前i个子串分割后是否存在于字典中。那么，这道题中存在这样的递推关系：F(0, i) = F(0, j) + F(j, i)，即前i个字符结果为true的充分条件是前j个字符结果为true，第j到i个子串结果也是true。

C++参考代码：

class Solution
    {
    public:
        bool wordBreak(string s, unordered_set<string> &dict)
        {
            string::size_type size = s.size();
            //申请size+1大小的空间，第一个设为true
            vector<bool> matches(size + 1, false);
            matches[0] = true;
            for (size_t i = 1; i <= size; ++i)
            {
                for (size_t j = 0; j < i; ++j)
                {
                    if (matches[j] && (dict.count(s.substr(j, i - j)) > 0))
                    {
                        matches[i] = true;
                        break;
                    }
                }
            }
            return matches[size];
        }
    };

C\#参考代码：

public class Solution
    {
        public bool WordBreak(string s, ISet<string> dict)
        {
            bool[] matches = new bool[s.Length + 1];
            matches[0] = true;
            for (int i = 1; i <= s.Length; ++i)
            {
                for (int j = 0; j < i; ++j)
                {
                    if (matches[j] && dict.Contains(s.Substring(j, i - j)))
                    {
                        matches[i] = true;
                        break;
                    }
                }
            }
            return matches[s.Length];
        }
    }

[Dynamic Programming]: http://blog.csdn.net/theonegis/article/details/44751991