首页 > 其他分享 >[代码随想录]Day40-动态规划part08

[代码随想录]Day40-动态规划part08

时间:2023-09-09 09:11:23浏览次数:47  
标签:part08 遍历 apple 随想录 单词 字典 true dp Day40

题目:139. 单词拆分

思路:

单词就是物品,字符串s就是背包,单词能否组成字符串s,就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词,说明就是一个完全背包!

动规五部曲分析如下:

  1. 确定dp数组以及下标的含义:dp[i] : 字符串长度为i的话,dp[i]为true,表示可以拆分为一个或多个在字典中出现的单词。

  2. 确定递推公式:如果确定dp[j] 是true,且 [j, i] 这个区间的子串出现在字典里,那么dp[i]一定是true。(j < i ),所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  3. dp数组如何初始化:从递推公式中可以看出,dp[i] 的状态依靠 dp[j]是否为true,那么dp[0]就是递推的根基,dp[0]一定要为true,否则递推下去后面都都是false了。

    那么dp[0]有没有意义呢?dp[0]表示如果字符串为空的话,说明出现在字典里。但题目中说了“给定一个非空字符串 s” 所以测试数据中不会出现i为0的情况,那么dp[0]初始为true完全就是为了推导公式。下标非0的dp[i]初始化为false,只要没有被覆盖说明都是不可拆分为一个或多个在字典中出现的单词。

  4. 确定遍历顺序:题目中说是拆分为一个或多个在字典中出现的单词,所以这是完全背包。还要讨论两层for循环的前后顺序。

    如果求组合数就是外层for循环遍历物品,内层for遍历背包如果求排列数就是外层for遍历背包,内层for循环遍历物品。而本题其实我们求的是排列数,为什么呢。 拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。"apple", "pen" 是物品,那么我们要求 物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的,那么我们就是强调物品之间顺序。所以说,本题一定是 先遍历 背包,再遍历物品。

代码:

func wordBreak(s string,wordDict []string) bool  {
	wordDictSet := make(map[string]bool)
	for _, w := range wordDict {
		wordDictSet[w] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			if dp[j] && wordDictSet[s[j:i]] { 
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

参考:

代码随想录

标签:part08,遍历,apple,随想录,单词,字典,true,dp,Day40
From: https://www.cnblogs.com/wtcsky/p/17688903.html

相关文章

  • 代码随想录刷题记录——栈与队列篇
    栈与队列理论基础 栈stack:先进后厨队列queue:先进先出STL(C++标准库)STL栈和队列属于容器适配器(containeradapter)优先队列priority_queue:默认大根堆,如果是pair<a,b>,默认比较a大小如果需要比较b大小,且小根堆,可以如下实现232.用栈实现队列题目链接 pop操作时,当......
  • 代码随想录算法训练营第二天| 977.有序数组的平方,209.长度最小的子数列,59.螺旋矩阵Ⅱ
    977.有序数组的平方双指针法因为负数平方后也会变大,所以较大的平方值只可能在靠近两端的位置,越往中间走平方值必定越小。所以,在原数组两端各定义一个指针,慢慢往中间走,然后把平方值按顺序放到新数组里即可。classSolution{public:vector<int>sortedSquares(vector<i......
  • 代码随想录刷题记录——双指针篇
    27.移除元素题目链接快慢指针,最终返回index值为移除元素后的数组末尾元素下标+1.#include<vector>usingnamespacestd;classSolution{public:intremoveElement(vector<int>&nums,intval){//快慢指针intnums_length=nums.size();......
  • 代码随想录个人笔记——字符串篇
    344.反转字符串 题目链接#include<bits/stdc++.h>usingnamespacestd;classSolution{public:voidreverseString(vector<char>&s){intlen=s.size();for(inti=0,j=len-1;i<j;i++,j--){//第一种//i......
  • 代码随想录算法训练营第二天
    代码随想录算法训练营第二天|LeetCode977(有序数组的平方)LeetCode209(长度最小的子数组)LeetCode59(螺旋矩阵II)977:有序数组的平方LeetCode977(有序数组的平方)思路:方法一:暴力方法直接原地平方后,直接调用数组排序方法二:双指针前后遍历,构造结果数组,保证有序方法......
  • 代码随想录算法第一天704
    代码随想录算法第一天|704.二分查找、27.移除元素学习(复习)数组理论基础:​ (https://programmercarl.com/数组理论基础.html)​ 新了解到Java中数组地址不是连续的。704.二分查找题目题目链接:https://leetcode.cn/problems/binary-search/文章讲解:https://programmercarl.......
  • 代码随想录算法训练营第一天
    代码随想录算法训练营第一天|LeetCode704(二分查找)LeetCode35(搜索插入位置)LeetCode34(在排序数组中查找元素的第一个和最后一个位置 )LeetCode27(移除元素)数组理论基础数组是存放在连续内存空间上的相同类型数据的集合要点:数组下标都是从0开始的数组内存空间......
  • 代码随想录算法训练营第十四天|二叉树的递归法、迭代法
    二叉树的递归遍历(前中后序遍历-递归法与迭代法)递归三部曲:确定递归函数的参数和返回值确定终止条件确定单层递归的逻辑递归法对二叉树进行前中后序遍历(力扣144.145.94.)//前序遍历·递归·LC144_二叉树的前序遍历classSolution{publicList<Integer>preorderTra......
  • 代码随想录算法训练营第二十九天| 491.递增子序列 46.全排列 47.全排列 II
     491.递增子序列   卡哥建议:本题和大家刚做过的 90.子集II 非常像,但又很不一样,很容易掉坑里。 https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html  视频讲解:https://www.bilibili.com/video/BV1EG4y1h78v  做题思路......
  • 代码随想录算法训练营第三十天| 51. N皇后 37. 解数独 总结
        卡哥建议:今天这三道题都非常难,那么这么难的题,为啥一天做三道? 因为 一刷 也不求大家能把这么难的问题解决,所以 大家一刷的时候,就了解一下题目的要求,了解一下解题思路,不求能直接写出代码,先大概熟悉一下这些题,二刷的时候,随着对回溯算法的深入理解,再去解决如下三题。 ......