n**e
发帖数: 116 | 1 Given a dictionary and a string, write a program to output the valid words
while minimizing the numbers of skipped characters. The substring that
consists of a valid word in the dictionary may swap the characters. For
example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
output is "window cat". In this case, there is only one number of skipped
character which is 'd'. |
n**e
发帖数: 116 | |
p*****2
发帖数: 21240 | |
w****x
发帖数: 2483 | 4 DP吧
rec[i], i 表示到index i截止skip掉的字符数
rec[i+1] = min( rec[j-1] + 1 if [j+1, i+1] can compose a word) j from i+1 to
0 |
p*****2
发帖数: 21240 | 5 嗯。DP可解。写起来比较麻烦。我要写就写recursion的了。 |
p*****2
发帖数: 21240 | 6
to
字典里的单词应该需要sort一下吧。
【在 w****x 的大作中提到】
: DP吧
: rec[i], i 表示到index i截止skip掉的字符数
: rec[i+1] = min( rec[j-1] + 1 if [j+1, i+1] can compose a word) j from i+1 to
: 0
|
Z*****Z
发帖数: 723 | 7
to
我觉得这个递归有问题，应该是
rec[i+1] = min{rec[i] + 1, rec[k] where 1<=k<=i and k to i+1 is a word}
【在 w****x 的大作中提到】
: DP吧
: rec[i], i 表示到index i截止skip掉的字符数
: rec[i+1] = min( rec[j-1] + 1 if [j+1, i+1] can compose a word) j from i+1 to
: 0
|
Z*****Z
发帖数: 723 | 8 对，这里的word都应该理解为anagram
【在 p*****2 的大作中提到】
:
: to
: 字典里的单词应该需要sort一下吧。
|
n**e
发帖数: 116 | 9 思路是对的，只是等搞明白问题后，剩下的时间很难写完程序。没有做好，浪费大好机
会。惭愧啊 |
w****x
发帖数: 2483 | 10
想这题就想了15分钟, 要我写肯定完蛋, 要输出skip的字符数还简单点, 要输出单词..
. XD
【在 n**e 的大作中提到】
: 思路是对的，只是等搞明白问题后，剩下的时间很难写完程序。没有做好，浪费大好机
: 会。惭愧啊
|
|
|
p*****2
发帖数: 21240 | 11
..
单词也可以。就是写起来麻烦些。主要是花时间。适合比赛用题，不适合面试。
【在 w****x 的大作中提到】
:
: 想这题就想了15分钟, 要我写肯定完蛋, 要输出skip的字符数还简单点, 要输出单词..
: . XD
|
n**e
发帖数: 116 | 12 我还是准备了DP问题的。但搞明白他的问题后，我真的就没有了信心些完程序。二爷说
的对，比赛可以，在面试时要求写代码，对我来说太难了。似乎今天的问题对我来说都
不太简单，但其他的还是完成了。总之实力不太够啊。 |
t********e
发帖数: 143 | 13
Nice. This is the trap. It is not important that characters are swapped.
Just compare them as anagram.
int minSkip(string &s, int start)
{
if (start == s.size())
return 0;
if (m[start] != -1)
return m[start];
//skip first char;
int min = minSkip(s, start+1) + 1;
//used first char case.
for (int i=start; i < s.size(); i++)
{
string sub = s.substr(start, i-start+1);
//use anagram compare for dict lookup
if (isInDict(sub))
{
int curMin = minSkip(s, i+1);
if (curMin < min)
min = curMin;
}
}
m[start] = min;
return min;
}
【在 Z*****Z 的大作中提到】
: 对，这里的word都应该理解为anagram
|
m***g
发帖数: 90 | 14 请问可以用hashmap把字典的字母和出现次数存起来，然后在字串里面一个个mapping吗
【在 p*****2 的大作中提到】
:
: ..
: 单词也可以。就是写起来麻烦些。主要是花时间。适合比赛用题，不适合面试。
|
q********c
发帖数: 1774 | 15 看来G的bar提高了不少，听说今年只招1000多,比去年的8000多可不是一个数量级的. |
b*****u
发帖数: 648 | 16 Can we interpret this as a backpack problem?
assume that there are k words in the dictionary, we can try 2^k times to see
which words combinations can fit in the character pool, then pick the least
cut one, right?
the
【在 n**e 的大作中提到】
: Given a dictionary and a string, write a program to output the valid words
: while minimizing the numbers of skipped characters. The substring that
: consists of a valid word in the dictionary may swap the characters. For
: example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
: output is "window cat". In this case, there is only one number of skipped
: character which is 'd'.
|
p*****2
发帖数: 21240 | 17
这样要很麻烦吧？要不就是我理解的不对。
【在 m***g 的大作中提到】
: 请问可以用hashmap把字典的字母和出现次数存起来，然后在字串里面一个个mapping吗
|
D********g
发帖数: 650 | 18 我觉得似乎还不对，应该是这样：
rec[i+1] = for all 1<=k<=i min{
rec[k], where k+1 to i+1 is a word (inclusive);
rec[k] + i+1 - k, where k+1 to i+1 is not a word (inclusive);
}
【在 Z*****Z 的大作中提到】
: 对，这里的word都应该理解为anagram
|
D********g
发帖数: 650 | 19 20分钟写了大约下面的code，如果要输出string，还要backtrack:
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
for (int i = 0; i < word.length(); ++i) {
int charVal = (int) word.charAt(i);
ht[charVal] ++;
}
StringBuilder anagram = new StringBuilder();
for (int i = 0; i < ht.length; ++i) {
if (ht[i] > 0) {
anagram.append((char)i).append(ht[i]);
}
}
return anagram.toString();
}
static Map> dict2Anagram(final Set dict) {
if (dict == null) {
return null;
}
final Map> anagrams = new HashMap
String>>();
for (final String word : dict) {
final String anagram = word2Anagram(word);
if (anagrams.containsKey(anagram)) {
anagrams.get(anagram).add(word);
} else {
List words = new ArrayList();
words.add(word);
anagrams.put(anagram, words);
}
}
return anagrams;
}
/*
*
Given a dictionary and a string, write a program to output the valid words
while minimizing the numbers of skipped characters. The substring that
consists of a valid word in the dictionary may swap the characters. For
example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
output is "window cat". In this case, there is only one number of skipped
character which is 'd'.
* */
static int findValidWordsWithMinSkip (final String input, final Set<
String> dict) {
if (input == null) {
throw new IllegalArgumentException("");
}
final Map> anagrams = dict2Anagram(dict);
int dp[] = new int[input.length() + 1];
for (int i = 1; i <= input.length(); ++i) {
int min = Integer.MAX_VALUE;
for (int j = 0; j < i; ++j) {
final String anagram = word2Anagram(input.substring(j, i));
if (anagrams.containsKey(anagram)) {
if (min > dp[j]) {
min = dp[j];
}
} else {
if (min > dp[j] + i - j) {
min = dp[j] + i - j;
}
}
}
dp[i] = min;
}
return dp[input.length()];
}
static void testFindValidWordsWithMinSkip () {
Set dict = new HashSet();
dict.add("window");
dict.add("cat");
String input = "iwndowdcta";
System.out.println(findValidWordsWithMinSkip(input, dict));
}
【在 D********g 的大作中提到】
: 我觉得似乎还不对，应该是这样：
: rec[i+1] = for all 1<=k<=i min{
: rec[k], where k+1 to i+1 is a word (inclusive);
: rec[k] + i+1 - k, where k+1 to i+1 is not a word (inclusive);
: }
|
Z*****Z
发帖数: 723 | 20 对，这个更完全，肯定是对的。
得想想我那个的反例。。。
【在 D********g 的大作中提到】
: 我觉得似乎还不对，应该是这样：
: rec[i+1] = for all 1<=k<=i min{
: rec[k], where k+1 to i+1 is a word (inclusive);
: rec[k] + i+1 - k, where k+1 to i+1 is not a word (inclusive);
: }
|
|
|
Z*****Z
发帖数: 723 | 21 牛，赞
【在 D********g 的大作中提到】
: 20分钟写了大约下面的code，如果要输出string，还要backtrack:
: static String word2Anagram(final String word) {
: if (word == null) {
: return null;
: }
:
: int ht[] = new int[256];
: for (int i = 0; i < word.length(); ++i) {
: int charVal = (int) word.charAt(i);
: ht[charVal] ++;
|
z********i
发帖数: 568 | 22 It seems to use the characters of the input string as many as possible to
form words in the dictionary and each character of the input string can be
used only once.
Is this the goal?
the
【在 n**e 的大作中提到】
: Given a dictionary and a string, write a program to output the valid words
: while minimizing the numbers of skipped characters. The substring that
: consists of a valid word in the dictionary may swap the characters. For
: example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
: output is "window cat". In this case, there is only one number of skipped
: character which is 'd'.
|
Z*****Z
发帖数: 723 | 23 不是吧，题目只是说在form word 的 substring里可以交换，没说任意两个字母可以交
换。
举例：字典是{input，many}，输入：ynputmani，并不是期望得到input和many
【在 z********i 的大作中提到】
: It seems to use the characters of the input string as many as possible to
: form words in the dictionary and each character of the input string can be
: used only once.
: Is this the goal?
:
: the
|
D********g
发帖数: 650 | 24 加上了backtracking:
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static String word2Anagram(final String word) {
if (word == null) {
return null;
}
int ht[] = new int[256];
for (int i = 0; i < word.length(); ++i) {
int charVal = (int) word.charAt(i);
ht[charVal] ++;
}
StringBuilder anagram = new StringBuilder();
for (int i = 0; i < ht.length; ++i) {
if (ht[i] > 0) {
anagram.append((char)i).append(ht[i]);
}
}
return anagram.toString();
}
static Map> dict2Anagram(final Set dict) {
if (dict == null) {
return null;
}
final Map> anagrams = new HashMap
String>>();
for (final String word : dict) {
final String anagram = word2Anagram(word);
if (anagrams.containsKey(anagram)) {
anagrams.get(anagram).add(word);
} else {
List words = new ArrayList();
words.add(word);
anagrams.put(anagram, words);
}
}
return anagrams;
}
/*
*
Given a dictionary and a string, write a program to output the valid words
while minimizing the numbers of skipped characters. The substring that
consists of a valid word in the dictionary may swap the characters. For
example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
output is "window cat". In this case, there is only one number of skipped
character which is 'd'.
* */
static List findValidWordsWithMinSkip (final String input, final
Set dict) {
if (input == null) {
throw new IllegalArgumentException("");
}
final Map> anagrams = dict2Anagram(dict);
DPElement dp[] = new DPElement[input.length() + 1];
for (int i = 0; i < dp.length; ++i) {
dp[i] = new DPElement();
}
for (int i = 1; i <= input.length(); ++i) {
int min = Integer.MAX_VALUE;
int minIdx = -1;
for (int j = 0; j < i; ++j) {
final String anagram = word2Anagram(input.substring(j, i));
if (anagrams.containsKey(anagram)) {
if (min > dp[j].value) {
min = dp[j].value;
minIdx = j;
}
} else {
if (min > dp[j].value + i - j) {
min = dp[j].value + i - j;
minIdx = j;
}
}
}
dp[i].value = min;
dp[i].prevCostIdx = minIdx;
}
List words = new ArrayList();
int idx = input.length();
while (idx > 0) {
int prevIdx = dp[idx].prevCostIdx;
if (dp[idx].value == dp[prevIdx].value) {
words.addAll(anagrams.get(word2Anagram(input.substring(
prevIdx, idx))));
}
idx = prevIdx;
}
return words;
}
static void testFindValidWordsWithMinSkip () {
Set dict = new HashSet();
dict.add("window");
dict.add("cat");
dict.add("act");
dict.add("widnow");
String input = "iwndowdcta";
System.out.println(findValidWordsWithMinSkip(input, dict));
} |
B*******1
发帖数: 2454 | 25 : int ht[] = new int[256];
: for (int i = 0; i < word.length(); ++i) {
: int charVal = (int) word.charAt(i);
: ht[charVal] ++;
Is this a bug?
dead - > ade ?
【在 D********g 的大作中提到】
: 20分钟写了大约下面的code，如果要输出string，还要backtrack:
: static String word2Anagram(final String word) {
: if (word == null) {
: return null;
: }
:
: int ht[] = new int[256];
: for (int i = 0; i < word.length(); ++i) {
: int charVal = (int) word.charAt(i);
: ht[charVal] ++;
|
p*****2
发帖数: 21240 | 26
大牛忙啥呢？怎么好久不见你了。
【在 B*******1 的大作中提到】
: : int ht[] = new int[256];
: : for (int i = 0; i < word.length(); ++i) {
: : int charVal = (int) word.charAt(i);
: : ht[charVal] ++;
: Is this a bug?
: dead - > ade ?
|
B*******1
发帖数: 2454 | 27 潜水学习呢。
★ 发自iPhone App: ChineseWeb - 中文网站浏览器
【在 p*****2 的大作中提到】
:
: 大牛忙啥呢？怎么好久不见你了。
|
p*****2
发帖数: 21240 | 28
已经修炼成精了把？
【在 B*******1 的大作中提到】
: 潜水学习呢。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
r*******t
发帖数: 99 | 29 这个题相当于一个Jump Game：一排格子，每一个可以往后面的某些格子里跳，每一跳
的cost是0。同时每一个可以往紧邻的下一个格子跳，每一跳的cost是1。把格子看成
vertex,跳看成edge的话就是一个directed graph的shortest path问题，而且这个图已
经是topologically ordered，只用从前往后scan一遍所有vertices，同时update当前
vertex前方与之相连的vertices就可以了。
每一个vertex有哪些outgoing的edges可以查用anagram索引过的dictionary来确定。索
引dictionary的时候记下最大词长可以减少look up的次数。
string minSkip(vector& dictionary, string& str) {
multimap ana2word;
size_t maxLength = 0;
for (size_t i = 0; i < dictionary.size(); ++i) {
string s = dictionary[i];
sort(s.begin(), s.end());
ana2word.insert(pair(s, dictionary[i]));
maxLength = max(maxLength, s.size());
}
vector minSkips(str.size() + 1, INT_MAX);
vector validWords(str.size() + 1);
minSkips[0] = 0;
for (size_t i = 0; i < str.size(); ++i) {
if (minSkips[i] + 1 < minSkips[i + 1]) {
minSkips[i + 1] = minSkips[i] + 1;
validWords[i + 1] = " ";
}
for (size_t n = 1; n <= min(maxLength, str.size() - i); ++n) {
string s = str.substr(i, n);
sort(s.begin(), s.end());
multimap::iterator it = ana2word.find(s);
if (it != ana2word.end() && minSkips[i] < minSkips[i + n]) {
minSkips[i + n] = minSkips[i];
validWords[i + n] = it->second;
}
}
}
string rtn;
for (size_t i = str.size(); i > 0; i -= validWords[i].size())
if (validWords[i] != " ")
rtn = validWords[i] + " " + rtn;
return rtn;
}
the
【在 n**e 的大作中提到】
: Given a dictionary and a string, write a program to output the valid words
: while minimizing the numbers of skipped characters. The substring that
: consists of a valid word in the dictionary may swap the characters. For
: example, Given a dictionary d = {window, cat} and a string "iwndowdcta", the
: output is "window cat". In this case, there is only one number of skipped
: character which is 'd'.
|
D********g
发帖数: 650 | 30 dead -> ad2e
【在 B*******1 的大作中提到】
: 潜水学习呢。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
|
|
D********g
发帖数: 650 | 31 dead -> ad2e
【在 B*******1 的大作中提到】
: 潜水学习呢。
:
: ★ 发自iPhone App: ChineseWeb - 中文网站浏览器
|
s********0
发帖数: 34 | 32 是我理解有问题么。
{"window", "cat"} "iwndowdcdta" 应该输出2 , skip第二个和第三个“d”
前面的dp好像没有考虑这种情况。。。
Please correct me if i'm wrong |
