【算法挨揍日记】day29——139. 单词拆分、467. 环绕字符串中唯一的子字符串

139. 单词拆分

139. 单词拆分

题目描述：

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

 解题思路：

解题代码：

class Solution {
public:
    bool wordBreak(string s, vector& wordDict) {
        unordered_set hash;
        for(auto& s : wordDict) hash.insert(s);
        int n=s.size();
        vector<bool>dp(n+1);
        dp[0]=true;
        s=' '+s;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j>=1;j--)
            {
                if(dp[j-1]==true&&hash.count(s.substr(j,i-j+1)))
                {
                    dp[i]=true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

---

467. 环绕字符串中唯一的子字符串

467. 环绕字符串中唯一的子字符串

题目描述：

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s ，请你统计并返回 s 中有多少 不同非空子串 也在 base 中出现。

 解题思路：

解题代码：

class Solution {
public:
    int findSubstringInWraproundString(string s) {
        int n=s.size();
        vector<int>dp(n,1);
        for(int i=1;i
        {
            if(s[i]-1==s[i-1]||(s[i-1]=='z'&&s[i]=='a'))
            dp[i]=dp[i-1]+1;
        }
      // 2. 计算每⼀个字符结尾的最⻓连续⼦数组的⻓度
 int hash[26] = { 0 };
 for(int i = 0 ; i < n; i++)
 hash[s[i] - 'a'] = max(hash[s[i] - 'a'], dp[i]);
 // 3. 将结果累加起来
 int sum = 0;
 for(auto x : hash) sum += x;
 
 return sum;
    }
};