期末算法夹缝求生(持续更新)

1. 知识点总结

emmm基本应该都是基础题，保持手感叭这段时间~

按照HOT前100的顺序，中间跳过部分水题（或者class类的题）

题目	知识点	难度
LRU缓存	STL容器，机试应该不怎会遇到，但是class确实写得少，练练不为过~之后回锅不需要反驳	🐸🐸
环形链表	链表	🐸
单词拆分	DP之后回锅不需要反驳	🐸🐸😇
环形链表	链表	没有难度
乘积最大子数字	==DP==?/可能就是简单的前缀和后缀也行叭，就是不美观	🐸🐸
打家劫舍	dp基础	🐸
岛屿数量	BFS基础	🐸
课程表	拓扑排序（不算难，但是模板忘记就凉凉）	🐸
最大正方形	单调栈（又忘了，照着模板写得呜呜）官方给的是DP，要回炉	🐸🐸🐸
二叉树的最近公共祖先	二叉树的遍历迭代、递推	🐸🐸
滑动窗口最大值	优先队列；后面两种没做（优化）单调队列；分块思想	🐸🐸🐸
搜索二维矩阵	……一言难尽准备回炉	🙄🙄
完全平方数	DP	🐸🐸🐸
移动零	数组操作	🐸
寻找相同的数	数组操作	🐸🐸
最大递增子序列	LIS经典题目，然鹅俺没AC😅回收预定	🐸🐸😤

2. 分题题解

2.1 单词拆分

脑子一抽想到的解法是暴力DFS，果然超时……直觉告诉我是DP，然后看了题解:感觉就是比较基础的DP,在区间[0,i]之间再找一个j作为切分点,经典思路哈

DFS暴力：38/45

class Solution {
public:
    int len;
    string ts;
    bool flag=false;
    map<string,bool>mp;
    void dfs(int pos,int L){
        string sub=ts.substr(pos,L);
        // cout<<sub<<"\n";
        if(mp.find(sub)==mp.end()){
            // cout<<"No!\n";
            return ;//找不到
        }else{
            //遍历其他可能
            // cout<<"Yes!\n";
            // cout<<pos+L<<"!!!\n";
            if(pos+L==len){
                flag=true;
                return;
            }
            for(int nL=1;pos+L+nL<=len;nL++){
                if(nL>20)break;
                dfs(pos+L,nL);
            }
        }
    }
    bool ch[26]={false};
    bool wordBreak(string s, vector<string>& wordDict) {
       len=s.length();
       ts=s;
       for(int i=0;i<wordDict.size();i++){
           mp[wordDict[i]]=true;
           for(int j=0;j<wordDict[i].size();j++){
               ch[wordDict[i][j]-'a']=true;
           }
       }
       //
       for(int i=0;i<len;i++){
           if(ch[ts[i]-'a']==false){
               return false;
           }
       }
       for(int i=1;i<=min(len,20);i++){
           dfs(0,i);
           if(flag==true){
               break;
           }
       }
       return flag;
    }
};

好像题解里面混入了一个耗时0ms的大神……不过是面向数据编程🤣，也是好强！

仔细研读了一下题解，做了简单复现+剪枝……这题不难，但是DP我感觉自己确实不是很上手，遇到这种题目条件反射是搜索

class Solution {
public:
    
    bool wordBreak(string s, vector<string>& wordDict) {
       int len=s.length();
       vector<bool>dp(len+1);
       map<string,bool>mp;
       int max_len=20;
       for(int i=0;i<wordDict.size();i++){
           mp[wordDict[i]]=true;
       }
       dp[0]=true;
       for(int i=1;i<=len;i++){
           for(int j=0;j<i;j++){
               if(i-j>max_len)continue;
              
               if(dp[j]&&mp.find(s.substr(j,i-j))!=mp.end()){
                   dp[i]=true;
                   
                   break;
               }
           }
       }
       return dp[len];
    }
};

2.2 环形链表

啊，数据结构基础，这个不兴不会哈

public:
    int sign=INT_MAX;//标记
    bool hasCycle(ListNode *head) {
        ListNode *p=head;
        while(p!=NULL){
            if(p->val==sign){
                return true;
            }
            p->val=sign;
            p=p->next;
        }
        return false;
    }
};

2.3 环形链表

因为给了数据的范围所以可以inf给遍历过的数据做标记，但这种解法适合考试不适合工程，相当于修改了用户数据了哈，虽然可耻但是有用（比官方的哈希快很多）

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户

内存消耗：7.6 MB, 在所有 C++ 提交中击败了23.74%的用户

class Solution {
public:
    const int inf=80000000;
    ListNode *detectCycle(ListNode *head) {
        ListNode* p=head;
        ListNode* pre=p;
        while(p!=NULL){
            if(p->val>=inf-1e5){//这里的判别注意一下，需要有范围的，如果题干不给范围就凉凉哈~
                p->val=p->val-inf;
                //cout<<p->val;
                return p;
            }
            p->val=p->val+inf;
            pre=p;
            p=p->next;
        }
        return NULL;
    }
};

2.4 LRU 缓存

我能说今天操作系统出分我还沉浸在悲伤中咩😓，想起了仓促复习的窘迫和出分的emmm

……时间到，STL的优先队列和运算符重载不熟练鉴定完毕，题解贴一下，下次补上

2.5 乘积最大子数组

考完模式识别回来写……主要是认知科学复习昂，背书背不动啦

• 暴力解法：TLE

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //感觉要用到大整数乘法
        int len=nums.size();
        vector<vector<int> >dp(len);
        for(int i=0;i<len;i++){
            dp[i].resize(len);
        }
        int ans=nums[0];
        for(int i=0;i<len;i++){
            dp[i][i]=nums[i];
            if(dp[i][i]>ans){
                ans=dp[i][i];
            }
            for(int j=i+1;j<len;j++){
                dp[i][j]=dp[i][j-1]*nums[j];
                if(dp[i][j]>ans){
                    ans=dp[i][j];
                }
            }
        }
        return ans;
    }
};

• 前缀、后缀的优化算法

执行用时：8 ms, 在所有 C++ 提交中击败了57.84%的用户

内存消耗：13.4 MB, 在所有 C++ 提交中击败了58.57%的用户

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        int len=nums.size();
        int temp=nums[0];
        int ans=nums[0];
        for(int i=1;i<len;i++){
            if(temp*nums[i]==0){
                temp=nums[i];
            }else{
                temp*=nums[i];
            }
            if(temp>ans)ans=temp;
            if(nums[i]>ans)ans=nums[i];
        }
        temp=nums[len-1];
        for(int i=len-2;i>=0;i--){
            if(temp*nums[i]==0){
                temp=nums[i];
            }else{
                temp*=nums[i];
            }
            if(temp>ans)ans=temp;
            
        }
        return ans;
    }
};

• 官方的题解感觉是更加合理的存在捏~标准动态规划！

2.6 打家劫舍

基础DP，没有凡学哈

class Solution {
public:
    int rob(vector<int>& nums) {
        //经典DP
        int len=nums.size();
        vector<vector<int> >dp(2,vector<int>(len));
        fill(dp[0].begin(),dp[0].end(),0);
        fill(dp[1].begin(),dp[1].end(),0);
        dp[1][0]=nums[0];
        for(int i=1;i<len;i++){
            dp[1][i]=nums[i]+dp[0][i-1];//上一次偷了的最大值
            dp[0][i]=max(dp[0][i-1],dp[1][i-1]);//上一次没偷的最大值
            //cout<<i<<":"<<max(dp[0][i],dp[1][i])<<endl;
        }
        return max(dp[0][len-1],dp[1][len-1]);
    }
};

2.7 岛屿数量

昂，基础BFS

class Solution {
public:
    struct Pos{
        int x,y;
    };
    int numIslands(vector<vector<char>>& grid) {
        //广度优先搜索或者深度优先搜索都可以哇，经典
        int n,m;
        n=grid.size();
        m=grid[0].size();
        vector<vector<bool> >vis(n,vector<bool>(m));
        for(int i=0;i<n;i++){
            fill(vis[i].begin(),vis[i].end(),false);
        }
        int ans=0;
        int dx[]={1,-1,0,0};
        int dy[]={0,0,1,-1};
        queue<Pos>q;Pos temp,top;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]=='1'&&!vis[i][j]){
                    ans++;
                   // cout<<i<<" "<<j<<"!!\n";
                    //BFS
                    temp.x=i;
                    temp.y=j;
                    q.push(temp);
                    vis[i][j]=true;
                    while(!q.empty()){
                        top=q.front();
                        q.pop();
                        for(int k=0;k<4;k++){
                            temp.x=top.x+dx[k];
                            temp.y=top.y+dy[k];
                            if(temp.x<n&&temp.x>=0&&temp.y>=0&&temp.y<m&&grid[temp.x][temp.y]=='1'&&!vis[temp.x][temp.y]){
                                q.push(temp);
                                vis[temp.x][temp.y]=true;
                               // cout<<temp.x<<" "<<temp.y<<"\n";
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
};

2.8 课程表

拓扑排序经典题，每次找出前序个数结点为0的进行遍历，同时以当前结点为前序的结点Node的前序节点个数–，若为0，加入queue队列中直到队列为空

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        //离散里面的先序的概念
        vector<vector<int> >afterIds(numCourses+1);
        vector<int>preNum(numCourses+1);
        fill(preNum.begin(),preNum.end(),0);
        int len=prerequisites.size();
        int a,b;
        for(int i=0;i<len;i++){
            a=prerequisites[i][0];
            b=prerequisites[i][1];
            afterIds[b].push_back(a);
            //先b后a
            preNum[a]++;
        }
        bool flag=true;
        queue<int>q;
        int cnt=0;
        for(int i=0;i<numCourses;i++){
            if(preNum[i]==0){
                q.push(i);
                cnt++;
            }
        }
        while(!q.empty()){
            //没有前序的结点,删除所有他后继节点
            b=q.front();
            q.pop();
            for(int i=0;i<afterIds[b].size();i++){
                a=afterIds[b][i];
                preNum[a]--;
                if(preNum[a]==0){
                    q.push(a);
                    cnt++;
                }
            }
        }
        //cout<<cnt<<endl;
        return flag&&(cnt>=numCourses);
    }
};

2.9 最大正方形

单调栈：需要注意i和j的顺序，然后就是最后判断最大值的时候min(横，竖)作为边长

执行用时：84 ms, 在所有 C++ 提交中击败了13.77%的用户

内存消耗：17.7 MB, 在所有 C++ 提交中击败了13.50%的用户

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        //类比于最大矩形的求法
        int ans=0;
        int m=matrix.size();//行
        int n=matrix[0].size();//列
        vector<vector<int> >histogram(m+1,vector<int>(n+1));
        //初始化直方图
        for(int i=0;i<m;i++){
            fill(histogram[i].begin(),histogram[i].end(),0);
            if((matrix[i][n-1]=='1')){
                histogram[i][n-1]=1;
                ans=1;
            }
            
            for(int j=n-2;j>=0;j--){
                if(matrix[i][j]=='1'){
                    ans=1;
                    histogram[i][j]=histogram[i][j+1]+1;
                }
            }
        }
       
        //下面对每一列采用单调栈
        vector<int>left(m);//这里就是上
        vector<int>right(m);//这里就是下
        stack<int>st;
        for(int i=0;i<n;i++){//列
            for(int j=0;j<m;j++){//行
                while(!st.empty()&&histogram[st.top()][i]>=histogram[j][i]){
                    st.pop();
                }
                left[j]=(st.empty()?-1:st.top());
                st.push(j);
            }
            while(!st.empty()){
                st.pop();
            }
            for(int j=m-1;j>=0;j--){
                while(!st.empty()&&histogram[st.top()][i]>=histogram[j][i]){
                    st.pop();
                }
                right[j]=(st.empty()?m:st.top());
                st.push(j);
            }
            while(!st.empty()){
                st.pop();
            }
            //遍历找最大值
            int temp=0;
            for(int j=0;j<m;j++){
                //cout<<i<<": "<<histogram[j][i]<<" "<<(right[j]-left[j]-1)<<"("<<left[j]<<","<<right[j]<<")"<<endl;
                //if((right[j]-left[j]-1)*histogram[j][i]>=1)temp=max(temp,1);
                int t=min((right[j]-left[j]-1),histogram[j][i]);
                temp=max(temp,t*t);
            }
            ans=max(ans,temp);
        }
        //返回最大值
        return ans;
    }
};

2.10 二叉树的最近公共祖先

我的直觉告诉我，这题之前PAT的甲级做过类似的……但是忘记了

写了一个比较复杂的，果然空间时间被吊打

执行用时：24 ms, 在所有 C++ 提交中击败了16.07%的用户

内存消耗：16.7 MB, 在所有 C++ 提交中击败了13.95%的用户

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    //层次遍历求父节点
    map<int,TreeNode*>fathers;//存储每个结点的父节点
    void levelTrace(TreeNode *root){
        //层次遍历
        queue<TreeNode*>q;
        q.push(root);
        TreeNode *top;
        while(!q.empty()){
            top=q.front();
            q.pop();
            if(top->left!=NULL){
                q.push(top->left);
                fathers[(top->left)->val]=top;
            }
            if(top->right!=NULL){
                q.push(top->right);
                fathers[(top->right)->val]=top;
            }
        }
    }
    int limit;
    vector<TreeNode*>Trace(int val){
        vector<TreeNode*>ans;
        int v=val;
        while(1){
            if(v==limit||fathers[v]==NULL){
                break;
            }
            ans.push_back(fathers[v]);
            v=fathers[v]->val;
        }
        return ans;
    }

    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
       limit=root->val;
       levelTrace(root);
       vector<TreeNode*>a=Trace(p->val);
       vector<TreeNode*>b=Trace(q->val);
       a.insert(a.begin(),p);
       b.insert(b.begin(),q);
       int lena=a.size();
       int lenb=b.size();
       int i=lena-1;
       int j=lenb-1;
       while(a[i]->val==b[j]->val){
           i--;
           j--;
           if(i<0||j<0){
               return a[i+1];
           }
       }
       return a[i+1];
    }
};

2.11 滑动窗口最大值

• 滑动窗口最大值 - 滑动窗口最大值 - 力扣（LeetCode）

暴力法可以通过47/50的案例，但是逃不掉TLE

• 暴力法

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int>ans;
        int len=nums.size();
        //最大值-最大值下标：尽可能靠右
        int maxIndex;
        int maxNum=-INT_MAX;
        //先找第一个的最大值
        for(int i=0;i<k;i++){
            if(nums[i]>=maxNum){
                maxNum=nums[i];
                maxIndex=i;
            }
        }
        ans.push_back(maxNum);
        int Left=0;
        int Right=k-1;
        
        for(int i=1;i<len-k+1;i++){
            Left++;
            Right++;
            //更新
            if(nums[Right]>=maxNum){
                maxNum=nums[Right];
                maxIndex=Right;
            }else if(maxIndex<Left){
                //需要重新找
                
                maxNum=-INT_MAX;
                for(int j=Left;j<=Right;j++){
                    
                    if(nums[j]>=maxNum){
                        maxNum=nums[j];
                        maxIndex=j;
                    }
                }
            }//否则保持原状
            
            ans.push_back(maxNum);
        }
        return ans;
    }
};

• 优先队列

老实说俺也想到了，但是C++好像没有提供删除指定元素的接口就放弃了，看了官方题解，表示有学到了新的知识~

priority_queue()默认是大顶堆~

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
       int len=nums.size();
       priority_queue<pair<int,int>>q;
       vector<int>ans;
       for(int i=0;i<k;i++){
           q.emplace(nums[i],i);//默认是大顶堆
       }
       int Right;
        for(int i=0;i<len-k+1;i++){
            Right=i+k-1;
            q.emplace(nums[Right],Right);
            while(q.top().second<i){
                q.pop();
            }
            ans.push_back(q.top().first);
        }
       return ans;
    }
};

另一种思路是单调队列

2.12 搜索二维矩阵

事实上是，这样做感觉和普通遍历没有区别，俺贴一下叭,二维的二分遍历我还是不熟练啊

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //好像写过：二分
        int m=matrix.size();
        int n=matrix[0].size();
        int up=0,down=m-1;
        int left=0,right=n-1;
        int hmid,wmid;
        bool flag=false;
        while(up<=down){
            hmid=up;
            left=0,right=n-1;
            if(target<matrix[hmid][left]){
                down=hmid-1;
            }else if(target>matrix[hmid][right]){
                up=hmid+1;
            }else{
                //在中间找
                while(left<=right){
                    wmid=(left+right)/2;
                    //cout<<hmid<<" "<<left<<" "<<right<<":"<<wmid<<"\n";
                    if(target==matrix[hmid][wmid]){
                        flag=true;
                        break;
                    }else if(target<matrix[hmid][wmid]){
                        right=wmid-1;
                    }else if(target>matrix[hmid][wmid]){
                        left=wmid+1;
                    }
                    
                }
                //如果中间查找失败的时候
                if(!flag){
                    if(hmid!=up){
                        hmid=up;
                        left=0;
                        right=n-1;
                        while(left<=right){
                            wmid=(left+right)/2;
                        if(target==matrix[hmid][wmid]){
                            flag=true;
                            break;
                        }else if(target<matrix[hmid][right]){
                            right=wmid-1;
                        }else if(target>matrix[hmid][left]){
                            left=wmid+1;
                            }
                        }
                    }
                }
                if(flag){
                    return flag;
                }else{
                    up++;
                }
            }
        }
        return flag;
    }
};

官方题解

翻官方题解发现了不得了的函数lower_bound,内置二分法查找

bool searchMatrix(vector<vector<int>>& matrix, int target) {
        for(const auto &row:matrix){
            auto it=lower_bound(row.begin(),row.end(),target);
            if(it!=row.end()&&*it==target){
                return true;
            }
        }
        return false;
    }

Z字型查找，我觉得如果抛弃一些模板思维，找规律的话还是很容易想到的？

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        //z字型查找
        int row=matrix.size();
        int col=matrix[0].size();
        int rx=0,ry=col-1;
        while(1){
            if(rx>=row||ry<0){
                break;
            }
            if(target==matrix[rx][ry]){
                return true;
            }
            if(target<matrix[rx][ry]){
                ry--;
            }else if(target>matrix[rx][ry]){
                rx++;
            }
        }
        return false;
    }
};

2.13 完全平方数

我猜是DP,但是没写对捏508/566

class Solution {
public:
    int numSquares(int n) {
        int len=int(sqrt(n)+0.5);
        int inf=100000;
        //初始化
        vector<vector<int> >f(len+1,vector<int>(n+1));
        for(int i=0;i<=len;i++){
            fill(f[i].begin(),f[i].end(),inf);
        }
        //f[i][j]，加入完全数i后，和为j的最小个数
        for(int i=1;i<=len;i++){
            f[i][0]=0;
            for(int j=1;j<=n;j++){
                for(int k=0;k*i*i<=j;k++){
                    if(f[i][j-k*i*i]==inf){
                        f[i][j-k*i*i]==min(j-k*i*i,f[i-1][j-k*i*i]);
                    }
                    if(f[i][j]==inf){
                        f[i][j]=min(j,f[i-1][j]);
                    }
                    f[i][j]=min(f[i][j],f[i][j-k*i*i]+k);
                }
                //cout<<"加入完全数"<<i*i<<"和为"<<j<<":"<<f[i][j]<<"\n";
            }

        }
        return f[len][n];
    }
};

确实是DP，并且蒙对了转移公式

class Solution {
public:
    int numSquares(int n) {
        int len=int(sqrt(n)+0.5);
        vector<int>dp(n+1);
        for(int j=0;j<=n;j++){
            dp[j]=j;
        }
        for(int i=1;i*i<=n;i++){
            dp[i*i]=1;
        }
        for(int i=1;i<=len;i++){
            for(int j=i*i;j<=n;j++){
                dp[j]=min(dp[j],dp[j-i*i]+dp[i*i]);
            }
        }
        return dp[n];
    }
};

2.13 移动零

还好吧，但是K·O有点打脸

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len=nums.size();
        //sign标志着最末尾一个不为0的数字的下标
        int sign=len-1;
        while(nums[sign]==0){
            sign--;
            if(sign==-1){
                return;
            }
        }
        //遍历数组
        for(int i=0;i<sign;i++){
            //cout<<i<<":"<<nums[i]<<"--"<<sign<<"\n";
            if(nums[i]==0){
                int temp=i;
                for(int j=i+1;j<=sign;j++){
                    swap(nums[i],nums[j]);
                    i++;
                }
                while(nums[sign]==0){
                    sign--;
                    if(sign==-1){
                        return;
                    }
                }
                i=temp;
                if(nums[i]==0){
                    i--;
                }
            }
        }
    }
};

2.14 寻找相同的数字

假设全都是不同的数字，根据数字的特性，不如假设nums[i]=i+1,所以解如下

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int len=nums.size();
        //不出意外的话，nums[i]==i+1;
        for(int i=0;i<len;i++){
           while(nums[i]!=i+1){
               //很重要的一个判断，即出现相同元素会死循环
               if(nums[i]==nums[nums[i]-1]){
                   return nums[i];
               }
               swap(nums[i],nums[nums[i]-1]);
           }
        }
        for(int i=0;i<len;i++){
            if(nums[i]!=i+1){
                return nums[i];
            }
        }
        return -1;
    }
};

2.15 寻找最大递增子序列

寻找最大递增子序列

• 错误的思路23/54

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //最长递增子序列
        int len=nums.size();
        vector<int>dp(len);
        fill(dp.begin(),dp.end(),1);
        vector<int>dpMax(len);
        dpMax[0]=nums[0];
        for(int i=1;i<len;i++){
            if(dp[i]<dp[i-1]+(nums[i]>dpMax[i-1])*1){
                dp[i]=dp[i-1]+(nums[i]>dpMax[i-1])*1;
                dpMax[i]=nums[i];
            }
            cout<<dp[i]<<" ";
        }

        return dp[len-1];
    }
};

• 尝试DFS暴力搜索22/54

啊，还是超时

class Solution {
public:
    int ans=1;
    int len;
    vector<int>v;
    void dfs(int index,int temp){
        ans=max(ans,temp);
        //dfs
        for(int i=index+1;i<len;i++){
            if(v[index]<v[i]){
                dfs(i,temp+1);
            }
        }
        return;
    }
    int lengthOfLIS(vector<int>& nums) {
        //最长递增子序列
        v=nums;
        len=nums.size();
        //DFS暴力
        for(int i=0;i<len;i++){
            dfs(i,1);
        }
        return ans;
    }
};

放弃，贴一下官方题解：

定义 dp[i] 为考虑前 i个元素，以第 i 个数字结尾的最长上升子序列的长度，注意 nums[i] 必须被选取。

我们从小到大计算 dp 数组的值，在计算dp[i] 之前，我们已经计算出dp[0…i−1] 的值，则状态转移方程为：

dp[i] = max(dp[j]) + 1）
dp[i]=max(dp[j])+1,其中0≤j<i且num[j]<num[i]

答案是最大的dp[i]对应的值

class Solution {
public:
    int ans=1;
    int len;
    
    int lengthOfLIS(vector<int>& nums) {
        len=nums.size();
        vector<int>dp(len,0);//初始化长度还有值
        for(int i=0;i<len;i++){
            dp[i]=1;//以第nums[i]结尾的递增数列的最大长度
            for(int j=0;j<i;j++){
                if(nums[i]>nums[j]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

3. 参考资料

单词拆分的官方题解

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        auto wordDictSet = unordered_set <string> ();
        for (auto word: wordDict) {
            wordDictSet.insert(word);
        }

        auto dp = vector <bool> (s.size() + 1);
        dp[0] = true;
        for (int i = 1; i <= s.size(); ++i) {
            for (int j = 0; j < i; ++j) {
                if (dp[j] && wordDictSet.find(s.substr(j, i - j)) != wordDictSet.end()) {
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[s.size()];
    }
};