C++实现LeetCode(139.拆分词句)

[LeetCode] 139. Word Break 拆分词句

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

Input: s = "leetcode", wordDict = ["leet", "code"]
Output: true
Explanation: Return true because

"leetcode"

can be segmented as

"leet code"

.

Example 2:

Input: s = "applepenapple", wordDict = ["apple", "pen"]
Output: true
Explanation: Return true because

"

applepenapple

"

can be segmented as

"

apple pen apple

"

.

             Note that you are allowed to reuse a dictionary word.

Example 3:

Input: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
Output: false

这道拆分词句问题是看给定的词句能分被拆分成字典里面的内容,这是一道很经典的题目,解法不止一种,考察的范围很广,属于我们必须要熟练掌握的题目。那么先来想 brute force 的解法,就拿例子1来分析,如果字典中只有两个单词,我们怎么去判断,是不是可以将原字符串s分成任意两段,然后再看分成的单词是否在字典中。注意这道题说是单词可以重复使用,所以可以分成任意段,而且字典中的单词可以有很多个,这就增加了题目的难度,很多童鞋就在这里迷失了,毫无头绪。

既然要分段,看子字符串是否在字典中,由于给定的字典是数组(之前还是 HashSet 呢),那么我们肯定不希望每次查找都需要遍历一遍数组,费劲!还是把字典中的所有单词都存入 HashSet 中吧,这样我们就有了常数时间级的查找速度,perfect!好,我们得开始给字符串分段了,怎么分,只能一个一个分了,先看第一个字母是否在字典中,如果不在的话,好办,说明这种分法肯定是错的。问题是在的话,后面的那部分怎么处理,难道还用 for 循环?咱也不知道还要分多少段,怎么用 for 循环。对于这种不知道怎么处理的情况,一个万能的做法是丢给递归函数,让其去递归求解,这里我们 suppose 递归函数会返回我们一个正确的值,如果返回的是 true 的话,表明我们现在分成的两段都在字典中,我们直接返回 true 即可,因为只要找出一种情况就行了。这种调用递归函数的方法就是 brute force 的解法,我们遍历了所有的情况,优点是写法简洁,思路清晰,缺点是存在大量的重复计算,被 OJ 啪啪打脸。所以我们需要进行优化,使用记忆数组 memo 来保存所有已经计算过的结果,再下次遇到的时候,直接从 cache 中取,而不是再次计算一遍。这种使用记忆数组 memo 的递归写法,和使用 dp 数组的迭代写法,乃解题的两大神器,凡事能用 dp 解的题,一般也有用记忆数组的递归解法,好似一对形影不离的好基友~关于 dp 解法,博主会在下文中讲解。这里我们的记忆数组 memo[i] 定义为范围为 [i, n] 的子字符串是否可以拆分,初始化为 -1,表示没有计算过,如果可以拆分,则赋值为1,反之为0。在之前讲 brute force 解法时,博主提到的是讲分成两段的后半段的调用递归函数,我们也可以不取出子字符串,而是用一个 start 变量,来标记分段的位置,这样递归函数中只需要从 start 的位置往后遍历即可,在递归函数更新记忆数组 memo 即可,参见代码如下:

解法一:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<int> memo(s.size(), -1);
        return check(s, wordSet, 0, memo);
    }
    bool check(string s, unordered_set<string>& wordSet, int start, vector<int>& memo) {
        if (start >= s.size()) return true;
        if (memo[start] != -1) return memo[start];
        for (int i = start + 1; i <= s.size(); ++i) {
            if (wordSet.count(s.substr(start, i - start)) && check(s, wordSet, i, memo)) {
                return memo[start] = 1;
            }
        }
        return memo[start] = 0;
    }
};

这道题其实还是一道经典的 DP 题目,也就是动态规划 Dynamic Programming。博主曾经说玩子数组或者子字符串且求极值的题,基本就是 DP 没差了,虽然这道题没有求极值,但是玩子字符串也符合 DP 的状态转移的特点。把一个人的温暖转移到另一个人的胸膛... 咳咳,跑错片场了,那是爱情转移~ 强行拉回,DP 解法的两大难点,定义 dp 数组跟找出状态转移方程,先来看 dp 数组的定义,这里我们就用一个一维的 dp 数组,其中 dp[i] 表示范围 [0, i) 内的子串是否可以拆分,注意这里 dp 数组的长度比s串的长度大1,是因为我们要 handle 空串的情况,我们初始化 dp[0] 为 true,然后开始遍历。注意这里我们需要两个 for 循环来遍历,因为此时已经没有递归函数了,所以我们必须要遍历所有的子串,我们用j把 [0, i) 范围内的子串分为了两部分,[0, j) 和 [j, i),其中范围 [0, j) 就是 dp[j],范围 [j, i) 就是 s.substr(j, i-j),其中 dp[j] 是之前的状态,我们已经算出来了,可以直接取,只需要在字典中查找 s.substr(j, i-j) 是否存在了,如果二者均为 true,将 dp[i] 赋为 true,并且 break 掉,此时就不需要再用j去分 [0, i) 范围了,因为 [0, i) 范围已经可以拆分了。最终我们返回 dp 数组的最后一个值,就是整个数组是否可以拆分的布尔值了,代码如下:

解法二:

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

下面我们从题目中给的例子来分析:

le e 

lee ee e 

leet 

leetc eetc etc tc c 

leetco eetco etco tco co o 

leetcod eetcod etcod tcod cod od d 

leetcode eetcode etcode tcode code 

T F F F T F F F T 

我们知道算法的核心思想是逐行扫描,每一行再逐个字符扫描,每次都在组合出一个新的字符串都要到字典里去找,如果有的话,则跳过此行,继续扫描下一行。

既然 DFS 都可以解题,那么 BFS 也就坐不住了,也要出来蹦跶一下。其实本质跟递归的解法没有太大的区别,递归解法在调用递归的时候,原先的状态被存入了栈中,这里 BFS 是存入了队列中,使用 visited 数组来标记已经算过的位置,作用跟 memo 数组一样,从队列中取出一个位置进行遍历,把可以拆分的新位置存入队列中,遍历完成后标记当前位置,然后再到队列中去取即可,参见代码如下:

解法三:

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> visited(s.size());
        queue<int> q{{0}};
        while (!q.empty()) {
            int start = q.front(); q.pop();
            if (!visited[start]) {
                for (int i = start + 1; i <= s.size(); ++i) {
                    if (wordSet.count(s.substr(start, i - start))) {
                        q.push(i);
                        if (i == s.size()) return true;
                    }
                }
                visited[start] = true;
            }
        }
        return false;
    }
};

到此这篇关于C++实现LeetCode(139.拆分词句)的文章就介绍到这了,更多相关C++实现拆分词句内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2021-07-18

C++实现LeetCode(86.划分链表)

[LeetCode] 86.Partition List 划分链表 Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. You should preserve the original relative order of the nodes in each of the two partitions

C++实现LeetCode(136.单独的数字)

[LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

C++实现LeetCode(89.格雷码)

[LeetCode] 89.Gray Code 格雷码 The gray code is a binary numeral system where two successive values differ in only one bit. Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code se

C++实现LeetCode(95.独一无二的二叉搜索树之二)

[LeetCode] 95. Unique Binary Search Trees II 独一无二的二叉搜索树之二 Given an integer n, generate all structurally unique BST's (binary search trees) that store values 1 ... n. Example: Input: 3 Output: [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3],

C++实现LeetCode(187.求重复的DNA序列)

[LeetCode] 187. Repeated DNA Sequences 求重复的DNA序列 All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA. Wr

C++实现LeetCode(93.复原IP地址)

[LeetCode] 93.Restore IP Addresses 复原IP地址 Given a string containing only digits, restore it by returning all possible valid IP address combinations. Example: Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"] 这

C++实现LeetCode(87.搅乱字符串)

[LeetCode] 87. Scramble String 搅乱字符串 Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively. Below is one possible representation of s1 = "great":     great /    \ gr    eat / \    /  \

C++实现LeetCode(137.单独的数字之二)

[LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

C++实现LeetCode(91.解码方法)

[LeetCode] 91. Decode Ways 解码方法 A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to

Python中json格式数据的编码与解码方法详解

本文实例讲述了Python中json格式数据的编码与解码方法.分享给大家供大家参考,具体如下: python从2.6版本开始内置了json数据格式的处理方法. 1.json格式数据编码 在python中,json数据格式编码使用json.dumps方法. #!/usr/bin/env python #coding=utf8 import json users = [{'name': 'tom', 'age': 22}, {'name': 'anny', 'age': 18}] #元组对象也可以

Python3内置模块之json编解码方法小结

Python3内置模块之json编解码方法小结 Python3中我们利用内置模块 json 解码和编码 JSON对象 ,JSON(JavaScript Object Notation)是指定 RFC 7159(废弃了RFC 4627)和 ECMA-404是一种轻量级数据交换格式,受 JavaScript对象文字语法的启发 (虽然它不是JavaScript 1的严格子集).下面为Python对象-->JSON对象的对照关系表. dumps编码 我们利用 dumps 将Python对象编码为 JSO

Java JDK1.7对字符串的BASE64编码解码方法

如下所示: package cn.itcast; import java.io.IOException; import java.io.UnsupportedEncodingException; import org.junit.Test; import sun.misc.BASE64Decoder; /* * @author soto * BASE64编码 解码 * */ public class Demo1 { @Test public void fun1() throws IOExcept

vscode+leetcode环境配置方法

前言 之前安装anaconda3的时候,选择了同时安装vscode,但从来没有正式去接触过它.最近,偶然想到看看leetcode,发现在vscode上搞leetcode很方便,于是就开始倒腾起来了. vscode配置 如何安装我就不详述了,win/ubuntu下的安装可参见我的博客: vscode+python+c++ 我现在的vscode的版本是:1.43.1 需要安装的插件有: anaconda extension pack: 支持非python官方的三方库code runner:F5快捷运

Python3内置模块之json编解码方法小结【推荐】

Python3中我们利用内置模块 json 解码和编码 JSON对象 ,JSON(JavaScript Object Notation)是指定 RFC 7159(废弃了RFC 4627)和 ECMA-404是一种轻量级数据交换格式,受 JavaScript对象文字语法的启发 (虽然它不是JavaScript 1的严格子集).下面为Python对象-->JSON对象的对照关系表. dumps编码 我们利用 dumps 将Python对象编码为 JSON对象 ,当然 dumps 只完成了序列化为st

Python JSON常用编解码方法代码实例

概念 JSON(JavaScript Object Notation) 是一种轻量级的数据交换格式,易于人阅读和编写.在日常的工作中,应用范围极其广泛.这里就介绍python下它的两种编解码方法: 使用json函数 使用 JSON 函数需要导入 json 库:import json.函数含义: 源码解析: # coding= utf-8 #!/usr/bin/python import json import sys data = {"username":"测试",

Python3内置模块之base64编解码方法详解

概述 Base64 是网络上最常见的用于传输 8Bit 字节码的编码方式之一,Base64 就是一种基于 64 个可打印字符来表示二进制数据的方法.可查看 RFC2045 - RFC2049,上面有 MIME 的详细规范.Base64 编码是从二进制到字符的过程,可用于在 HTTP 环境下传递较长的标识信息.比如使二进制数据可以作为电子邮件的内容正确地发送,用作 URL 的一部分,或者作为 HTTP POST 请求的一部分. 即 base64 其实不能归属密码领域,作用也不是用于加密,它是一种编

Javascript下的urlencode编码解码方法附decodeURIComponent

关于在ASP(Server.UrlEncode).PHP(urlencode())函数编码结果,或是经过asp.php等动态语言直接写入COOKIES的中文字符,用JS读取的时候,都会碰到一个编码的问题,那就是最终字符串被urlencode编码了,而又时有需要从JS在客户端去读取这些数据. 而本文,就大概说说如何在js中通过系统自带的函数去解决这个问题. 而相信碰到过此问题的朋友应该都有所了解,目前网络上流行一些js下的自定义函数去解决这个问题,如说vbscript(URLDecode()).j

Python3 JSON编码解码方法详解

JSON(JavaScript Object Notation)是一种轻量级的数据交换格式,它基于ECMAScript的一个子集. JSON采用完全独立于语言的文本格式,这些特性使JSON成为理想的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成,在接口数据开发和传输中非常常用. Python3中我们利用内置模块json解码和编码JSON对象.json模块提供了四个功能:dumps.dump.loads.load dumps 把数据类型转换成字符串 dump 把数据类型转换成字符串并存储

java中文乱码之解决URL中文乱码问题的方法

我们主要通过两种形式提交向服务器发送请求:URL.表单.而表单形式一般都不会出现乱码问题,乱码问题主要是在URL上面.通过前面几篇博客的介绍我们知道URL向服务器发送请求编码过程实在是实在太混乱了.不同的操作系统.不同的浏览器.不同的网页字符集,将导致完全不同的编码结果.如果程序员要把每一种结果都考虑进去,是不是太恐怖了?有没有办法,能够保证客户端只用一种编码方法向服务器发出请求? 有!这里我主要提供以下几种方法 一.javascript 使用javascript编码不给浏览器插手的机会,编码之