加上了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 HashMapString>>();
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));
}
