f*********d
发帖数: 140 | 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’.
多维背包？但是这个维度(#of alphas in language)还是太高了吧。有其它好的解法吗？ | a********m
发帖数: 15480 | 2 每个词都可以用一个长度＃的数组表示，然后把字典建成一个＃维数组。最后背包部分
还算可以接受吧，少于＃维恐怕难。 | f*********d
发帖数: 140 | 3 借这题再问大牛一个相关的问题，如果维度不确定的dp，比如说依赖于输入，那在实现
上好做吗？ 具体一点的等价问题，如果知道是26维dp，可以避免写26层的循环吗？也
许借助递归可以很好的实现，记忆化dp？ 请大牛confirm一下！
【在 a********m 的大作中提到】
: 每个词都可以用一个长度＃的数组表示，然后把字典建成一个＃维数组。最后背包部分
: 还算可以接受吧，少于＃维恐怕难。
| b**m
发帖数: 1466 | 4 如果我没理解错的话,
可以简化为shortest path 问题。
不过这种题我得想20分钟才能想出思路来。 | p*u
发帖数: 136 | 5 感觉这是个网络流问题。
假设词典有n个单词，每个单词最后在string中出现的次数为f[i]，根据26个字母，可
以列26个不等式，比如例子中w的不等式为：
2 * f[0] + 0 * f[1] <= 2
目标方程：z = len(string) - f[0] * len(dict[0]) - f[1] * len(dict[1]) - ...
求z的最小值，用网络流的方法就可以了。
the
skipped
吗？
【在 f*********d 的大作中提到】
: 继续问题，跪求大牛帮忙扫:)
: 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’.
: 多维背包？但是这个维度(#of alphas in language)还是太高了吧。有其它好的解法吗？
| a********m
发帖数: 15480 | 6 赞。
【在 p*u 的大作中提到】
: 感觉这是个网络流问题。
: 假设词典有n个单词，每个单词最后在string中出现的次数为f[i]，根据26个字母，可
: 以列26个不等式，比如例子中w的不等式为：
: 2 * f[0] + 0 * f[1] <= 2
: 目标方程：z = len(string) - f[0] * len(dict[0]) - f[1] * len(dict[1]) - ...
: 求z的最小值，用网络流的方法就可以了。
:
: the
: skipped
: 吗？
| a********m
发帖数: 15480 | 7 多维背包记得不需要那么多循环。实现上应该区别不大，递归应该是要用到。不过这题
写起来恐怕挺麻烦的。
【在 f*********d 的大作中提到】
: 借这题再问大牛一个相关的问题，如果维度不确定的dp，比如说依赖于输入，那在实现
: 上好做吗？ 具体一点的等价问题，如果知道是26维dp，可以避免写26层的循环吗？也
: 许借助递归可以很好的实现，记忆化dp？ 请大牛confirm一下！
| t****a
发帖数: 1212 | 8 可以用DP来做。计算复杂度大约为n^3*len(dict)
假设输入字符串s长度为n，f为求解的函数，那么
f(s, dict) = match_dict(s, dict) 当s可以直接匹配上dict里的某字符串（通过排序
后比较）, match_dict返回dict中匹配上的字符串
f(s, dict) = (max the words length) [f(subs(s, 0, i), dict), f(subs(s, i, n)
, dict)], i=1..n-1 当s不能直接找到dict里的匹配
f(s, dict) = nil 当s为空
clojure程序如下
(defn gen-sorted-dict [dict]
(reduce merge (for [w dict]
{(sort w) w})))
(defn match-dict [s sorted-dict]
(sorted-dict (sort s)))
(def prob10-sub
(memoize
(fn [s sorted-dict]
(when (not (empty? s))
(if-let [mw (match-dict s sorted-dict)]
[mw]
(let [mws (for [i (range 1 (count s))
:let [s1 (subs s 0 i)
m1 (prob10-sub s1 sorted-dict)
s2 (subs s i)
m2 (prob10-sub s2 sorted-dict)
m12 (concat m1 m2)]
:when (not (empty? m12))]
m12)]
(first (sort-by #(reduce + (map count %)) > mws))))))))
(defn prob10 [s dict]
(prob10-sub s (gen-sorted-dict dict)))
(prob10 "iwndowdcta" ["window" "cat"]) ;("window" "cat")
(prob10 "iwndowdctatc" ["windowdc" "cat"]) ;("windowdc" "cat") | c*****n
发帖数: 83 | 9 用二维 DP 做:
Define f_k(i) the number of skipped characters with string s[i,i+k).
Starting from k = 1 initializing f_1(i) = 0 if s[i] is in dict, f_1(i) = 1
otherwise; then calculate f_{k}(i) recursively by
f_{k+1}(i) = min_{h=1}^{k} {f_h(i) + f_{k+1-h}(i+h)} if s[i,i+k+1) is NOT in
dict; otherwise f_{k+1}(i) = 0;
up to k = len(s)
如何判断 s[i,i+k) is in Dict? One-pass preprocessing
Sol(1): the signatures of all words in Dict: the frequencies of letters in
that word, 然后按这个 signature 排序。
Sol(2): Hash table all words | c********e
发帖数: 186 | 10 觉得一维dp就可以了
F(0) = 0;
string s, length N
i=1, 2, ..., N
F(i) = Min_j (F(j-1)+ isDict(s(j-1,i)) ? 0 : i-j+1 ) where j = i,...,1
s(j-1,i) includes chars [j-1, i)
in
【在 c*****n 的大作中提到】
: 用二维 DP 做:
: Define f_k(i) the number of skipped characters with string s[i,i+k).
: Starting from k = 1 initializing f_1(i) = 0 if s[i] is in dict, f_1(i) = 1
: otherwise; then calculate f_{k}(i) recursively by
: f_{k+1}(i) = min_{h=1}^{k} {f_h(i) + f_{k+1-h}(i+h)} if s[i,i+k+1) is NOT in
: dict; otherwise f_{k+1}(i) = 0;
: up to k = len(s)
: 如何判断 s[i,i+k) is in Dict? One-pass preprocessing
: Sol(1): the signatures of all words in Dict: the frequencies of letters in
: that word, 然后按这个 signature 排序。
|
|
