《Cracking the Coding Interview》——第17章:普通题——题目14
2024-09-01 18:47:57
2014-04-29 00:20
题目:给定一个长字符串,和一个词典。如果允许你将长串分割成若干个片段,可能会存在某些片段在词典里查不到,有些则查得到。请设计算法进行分词,使得查不到的片段个数最少。
解法:用空间换取时间的动态规划算法,首先用O(n^2)的时间判断每一个片段是否在字典里。这个过程其实可以通过字典树来进行加速,时间上能优化一个阶,不过我没写,偷懒用<unordered_set>代表了字典。之后通过O(n)时间的动态规划,dp[i]表示当前位置的查不到的片段的最少个数。对于懂代码的人,代码说的比文字清楚,所以请看代码。
代码:
// 17.14 Given a dictionary of words, and a long string. You may find a way to cut the string into words, where some of them may or may not be in the dictionary.
// Dynamic programming is a good thing, but trades space in for time.
#include <iostream>
#include <string>
#include <unordered_set>
#include <vector>
using namespace std; int main()
{
string data;
unordered_set<string> dict;
vector<vector<bool> > contains;
vector<int> dp;
int i, j;
string s;
int n;
int tmp; while (cin >> data && data != "") {
cin >> n;
for (i = ; i < n; ++i) {
cin >> s;
dict.insert(s);
}
n = (int)data.length(); contains.resize(n);
for (i = ; i < n; ++i) {
contains[i].resize(n);
}
for (i = ; i < n; ++i) {
s = "";
for (j = i; j < n; ++j) {
s.push_back(data[j]);
contains[i][j] = (dict.find(s) != dict.end());
}
} dp.resize(n);
for (i = ; i < n; ++i) {
dp[i] = contains[][i] ? : i + ;
for (j = ; j < i; ++j) {
tmp = dp[j] + (contains[j + ][i] ? : i - j);
dp[i] = dp[i] < tmp ? dp[i] : tmp;
}
} printf("%d\n", dp[n - ]); for (i = ; i < n; ++i) {
contains[i].clear();
}
contains.clear();
dp.clear();
dict.clear();
} return ;
}
最新文章
- Node.js大众点评爬虫
- static方法中为什么使用的都是静态变量
- FZU 2082 过路费
- centos下安装node js
- c#与java webservice调用问题
- 20151207jquery 学习笔记 Ajax
- 705 - Slash Maze
- 可持久化Trie树初步
- js随机模块颜色
- Java 删除项目中的.svn信息
- 删数方案数(regex)
- restful设计规范
- python框架之Flask(1)-Flask初使用
- API输出的时候是return还是echo?
- 关于hover的一个问题记录
- Vue笔记:使用 vuex 管理应用状态
- Java - 30 Java 网络编程
- gRPC版本的 Google APIs
- 【题解】洛谷P1373 小a和uim之大逃离(坐标DP)
- c艹第三次作业
热门文章
- 进程—内存描述符(mm_struct)
- 前端高质量知识(二)-JS执行上下文(执行环境)详细图解Script
- BestCoder Round #91 1002 Lotus and Horticulture
- python 下实现window 截图
- 运行时库例程-acc_get_num_devices
- 第30章 	ADC—电压采集—零死角玩转STM32-F429系列
- 121. Best Time to Buy and Sell Stock——Leetcode
- 子div作为遮罩层
- python while循环与for循环
- 关于新项目上传远程库报错 non-fast-forward