java使用给定的单词列表重新创建给定字符串的多种方法

Question

给定的是一个字符串word和一个包含一些字符串的字符串数组book。程序应该给出仅使用book中的元素创建word的可能性数量。一个元素可以使用任意次数，程序必须在6秒内终止

例如，输入：

String word = "stackoverflow";

String[] book = new String[9];
book[0] = "st";
book[1] = "ck";
book[2] = "CAG";
book[3] = "low";
book[4] = "TC";
book[5] = "rf";
book[6] = "ove";
book[7] = "a";
book[8] = "sta";

输出应该是2，因为我们可以通过两种方式创建"stackoverflow"：

1:"st"+"a"+"ck"+"ove"+"rf"+"low"

2:"sta"+"ck"+"ove"+"rf"+"low"

如果word相对较小（<；15个字符），我的程序实现仅在所需时间内终止。但是，正如我前面提到的，程序的运行时间限制是6秒，它应该能够处理非常大的word字符串（>；1000个字符）Here是大型输入的一个示例

这是我的密码：

1）实际方法：

输入：字符串word和字符串[]book

输出：仅使用书本中的字符串写入单词的方式数

public static int optimal(String word, String[] book){
    int count = 0;

    List<List<String>> allCombinations = allSubstrings(word);

    List<String> empty = new ArrayList<>();

    List<String> wordList = Arrays.asList(book);

    for (int i = 0; i < allCombinations.size(); i++) {

        allCombinations.get(i).retainAll(wordList);

        if (!sumUp(allCombinations.get(i), word)) {
            allCombinations.remove(i);
            allCombinations.add(i, empty);
        }
        else count++;
    }

    return count;
}

2）所有子字符串（）：

输入：字符串input

输出：一个列表列表，每个列表包含一组子字符串，这些子字符串加起来就是输入

static List<List<String>> allSubstrings(String input) {

    if (input.length() == 1) return Collections.singletonList(Collections.singletonList(input));

    List<List<String>> result = new ArrayList<>();

    for (List<String> temp : allSubstrings(input.substring(1))) {

        List<String> firstList = new ArrayList<>(temp);
        firstList.set(0, input.charAt(0) + firstList.get(0));
        if (input.startsWith(firstList.get(0), 0)) result.add(firstList);

        List<String> l = new ArrayList<>(temp);
        l.add(0, input.substring(0, 1));
        if (input.startsWith(l.get(0), 0)) result.add(l);
    }

    return result;
}

(三)总结（）：

输入：字符串列表input和字符串expected

输出：如果input中的元素加起来等于expected，则为true

public static boolean sumUp (List<String> input, String expected) {

    String x = "";

    for (int i = 0; i < input.size(); i++) {
        x = x + input.get(i);
    }
    if (expected.equals(x)) return true;
    return false;
}

Answer 1

我发现我在my previous answer中做错了什么：我没有使用回忆录，所以我在重做大量不必要的工作

考虑一个书数组^ {< CD1>}和一个目标词^ {< CD2>}。有四种方法可以构建这个目标：

"a" + "a" + "a"
"aa" + "a"
"a" + "aa"
"aaa"

我之前的尝试将分别通过这四个步骤。但是，我们可以观察到：

• 有一种方法可以构造"a"
• 你可以用两种方式来构建"aa"，要么"a" + "a"要么直接使用"aa"
• 您可以直接使用"aaa"来构造"aaa"（1种方式）；或者"aa" + "a"（两种方式，因为有两种方式来构建"aa"）；或者"a" + "aa"（单向）

请注意，这里的第三步只在先前构造的字符串中添加了一个额外的字符串，我们知道可以用多少种方法构造它

这表明，如果我们计算word前缀的构造方式的数量，我们可以通过从book中再添加一个字符串来计算更长前缀的方式的数量

我定义了一个简单的trie类，因此您可以快速查找book单词的前缀，这些前缀在word中的任何给定位置都匹配：

class TrieNode {
  boolean word;
  Map<Character, TrieNode> children = new HashMap<>();

  void add(String s, int i) {
    if (i == s.length()) {
      word = true;
    } else {
      children.computeIfAbsent(s.charAt(i), k -> new TrieNode()).add(s, i + 1);
    }
  }
}

对于s中的每个字母，这将创建TrieNode的一个实例，并为后续字符等存储TrieNode

static long method(String word, String[] book) {
  // Construct a trie from all the words in book.
  TrieNode t = new TrieNode();
  for (String b : book) {
    t.add(b, 0);
  }

  // Construct an array to memoize the number of ways to construct
  // prefixes of a given length: result[i] is the number of ways to
  // construct a prefix of length i.
  long[] result = new long[word.length() + 1];

  // There is only 1 way to construct a prefix of length zero.
  result[0] = 1;

  for (int m = 0; m < word.length(); ++m) {
    if (result[m] == 0) {
      // If there are no ways to construct a prefix of this length,
      // then just skip it.
      continue;
    }

    // Walk the trie, taking the branch which matches the character
    // of word at position (n + m).
    TrieNode tt = t;
    for (int n = 0; tt != null && n + m <= word.length(); ++n) {
      if (tt.word) {
        // We have reached the end of a word: we can reach a prefix
        // of length (n + m) from a prefix of length (m).
        // Increment the number of ways to reach (n+m) by the number
        // of ways to reach (m).
        // (Increment, because there may be other ways).
        result[n + m] += result[m];
        if (n + m == word.length()) {
          break;
        } 
      }
      tt = tt.children.get(word.charAt(n + m));
    }
  }

  // The number of ways to reach a prefix of length (word.length())
  // is now stored in the last element of the array.
  return result[word.length()];
}

对于very long input given by OP，这将提供以下输出：

$ time java Ideone

2217093120

real    0m0.126s
user    0m0.146s
sys 0m0.036s

比所需的6秒要快很多——这也包括JVM启动时间

---

编辑：事实上，trie不是必需的。您可以简单地用以下内容替换“在trie中行走”循环：

for (String b : book) {
  if (word.regionMatches(m, b, 0, b.length())) {
    result[m + b.length()] += result[m];
  }
}

它的运行速度比6s慢，但仍然快得多：

2217093120

real    0m0.173s
user    0m0.226s
sys 0m0.033s

Answer 2

以下是一些观察：

x = x + input.get(i);

在循环时，使用String+不是一个好主意。使用StringBuilder并附加到循环中的StringBuilder，最后return builder.toString()。或者你跟随安迪的想法。不需要合并字符串，您已经知道目标单词。见下文

然后：List意味着添加/删除元素可能代价高昂。所以，看看你是否能摆脱这一部分，如果有可能使用地图，集代替

最后：真正的重点是研究你的算法。我会努力“向后”工作。意思：首先确定那些在目标词中实际出现的数组元素。你可以从一开始就忽略其他人

然后：查看**开始*+搜索词的所有数组条目。在您的示例中，您可以注意到只有两个适合的数组元素。然后从那里开始工作

Answer 3

我认为你在优化应用程序方面已经做得很好了。除了幽灵猫的回答之外，我还有几点建议：

public static int optimal(String word, String[] book){

    int count = 0;

    List<List<String>> allCombinations = allSubstrings(word);
    List<String> wordList = Arrays.asList(book);

    for (int i = 0; i < allCombinations.size(); i++)
    {
        /*
         * allCombinations.get(i).retainAll(wordList);
         * 
         * There is no need to retrieve the list element
         * twice, just set it in a local variable
         */
        java.util.List<String> combination = allCombinations.get(i);
        combination.retainAll(wordList);
        /*
         * Since we are only interested in the count here
         * there is no need to remove and add list elements
         */
        if (sumUp(combination, word)) 
        {
            /*allCombinations.remove(i);
            allCombinations.add(i, empty);*/
            count++;
        }
        /*else count++;*/
    }
    return count;
}

public static boolean sumUp (List<String> input, String expected) {

    String x = "";

    for (int i = 0; i < input.size(); i++) {
        x = x + input.get(i);
    }
    // No need for if block here, just return comparison result
    /*if (expected.equals(x)) return true;
    return false;*/
    return expected.equals(x);
}

由于您对查看方法的执行时间感兴趣，我建议您实施某种基准测试系统。下面是一个快速的模型：

private static long benchmarkOptima(int cycles, String word, String[] book) {

    long totalTime = 0;
    for (int i = 0; i < cycles; i++)
    {
        long startTime = System.currentTimeMillis();

        int a = optimal(word, book);

        long executionTime = System.currentTimeMillis() - startTime;
        totalTime += executionTime;
    }
    return totalTime / cycles;
}

public static void main(String[] args)
{
    String word = "stackoverflow";
    String[] book = new String[] {
            "st", "ck", "CAG", "low", "TC",
            "rf", "ove", "a", "sta"
    };

    int result = optimal(word, book);

    final int cycles = 50;
    long averageTime = benchmarkOptima(cycles, word, book);

    System.out.println("Optimal result: " + result);
    System.out.println("Average execution time - " + averageTime + " ms");
}

输出

2
Average execution time - 6 ms

Answer 4

注意：这个实现被@user1221提到的测试用例卡住了，正在处理它

我能想到的是一种基于Trie的方法，即O(sum of length of words in dict)空间。时间不是最佳选择

程序：

1. 把字典里的所有单词都拼凑起来。这是一项预处理任务，需要O(sum of lengths of all strings in dict)
2. 我们试着在trie中找到你想做的线，并进行扭转。我们首先搜索字符串的前缀。如果我们在trie中得到一个前缀，我们将从顶部递归地开始搜索，并继续寻找更多的前缀
3. 当我们到达out字符串的末尾时，即stackoverflow，我们检查是否到达任何字符串的末尾，如果是，则我们到达该字符串的有效组合。我们在返回递归时计算这个

例如： 在上面的例子中，我们使用dict作为{"st", "sta", "a", "ck"} 我们构造我们的trie（$是sentinel字符，即不在dict中的字符）：

$___s___t.___a.
|___a.
|___c___k.

.表示dict中的一个单词在该位置结束。 我们试图找出stack结构的数量

我们开始在trie中搜索stack

depth=0
$___s(*)___t.___a.
|___a.
|___c___k.

我们看到我们在一个单词的末尾，我们用顶部剩余的字符串ack开始新的搜索

depth=0
$___s___t(*).___a.
|___a.
|___c___k.

再一次，我们在dict中一个单词的末尾。我们开始新的ck搜索

depth=1
$___s___t.___a.
|___a(*).
|___c___k.

depth=2
$___s___t.___a.
|___a.
|___c(*)___k.

我们到达了stack的结尾和dict中一个单词的结尾，因此我们有一个有效的stack表示

depth=2
$___s___t.___a.
|___a.
|___c___k(*).

我们回到调用depth=2

没有下一个字符可用，我们返回depth=1的调用者

depth=1
$___s___t.___a.
|___a(*, 1).
|___c___k.

depth=0
$___s___t(*, 1).___a.
|___a.
|___c___k.

我们转到下一个字符。我们看到我们到达了dict中一个单词的末尾，我们在dict中启动了一个新的搜索ck

depth=0
$___s___t.___a(*, 1).
|___a.
|___c___k.

depth=1
$___s___t.___a.
|___a.
|___c(*)___k.

我们到达了stack的结尾，并且在dict中完成了一个工作，所以又是一个有效的表示。我们回到调用depth=1

depth=1
$___s___t.___a.
|___a.
|___c___k(*, 1).

没有更多的字符要继续，我们返回结果2

depth=0
$___s___t.___a(*, 2).
|___a.
|___c___k.

<强>注：实现是C++，不太难转换为java，这个实现假定所有字符都是小写的，将它扩展到两种情况都很微不足道。p>

示例代码（full version）：

/**
Node *base: head of the trie
Node *h   : current node in the trie
string s  : string to search
int idx   : the current position in the string
*/
int count(Node *base, Node *h, string s, int idx) {
    // step 3: found a valid combination.
    if (idx == s.size()) return h->end;

    int res = 0;
    // step 2: we recursively start a new search.
    if (h->end) {
        res += count(base, base, s, idx);
    }
    // move ahead in the trie.
    if (h->next[s[idx] - 'a'] != NULL) { 
        res += count(base, h->next[s[idx] - 'a'], s, idx + 1);
    }

    return res;
}

Answer 5

我的第一个观察结果是，你实际上不需要构建任何东西：你知道你要构建什么字符串（例如^{），所以你真正需要跟踪的是你到目前为止匹配了多少字符串。称之为m

接下来，在匹配了m个字符之后，提供了m < word.length()，您需要从book中选择下一个字符串，该字符串匹配word从m到m + nextString.length()的部分

可以通过依次检查每个字符串来实现：

if (word.matches(m, nextString, 0, nextString.length()) { ...}

但是，通过提前确定无法匹配的字符串，您可以做得更好：您附加的下一个字符串将具有以下属性：

1. word.charAt(m) == nextString.charAt(0)（下一个字符匹配）
2. m + nextString.length() <= word.length()（添加下一个字符串不应使构造的字符串超过word）

所以，你可以通过构建一个字母到以字母开头的单词的映射图（第1点）来减少书中可能要检查的潜在单词；如果你把同一个起始字母的单词按长度递增的顺序存储起来，一旦长度过大，你就可以停止检查这个字母（第2点）

您可以一次性构建地图并重复使用：

Map<Character, List<String>> prefixMap =
    Arrays.asList(book).stream()
        .collect(groupingBy(
            s -> s.charAt(0),
            collectingAndThen(
                toList(),
                ss -> {
                  ss.sort(comparingInt(String::length));
                  return ss;
                })));

您可以递归地计算方法的数量，而无需构造任何其他对象（*）：

int method(String word, String[] book) {
  return method(word, 0, /* construct map as above */);
}

int method(String word, int m, Map<Character, List<String>> prefixMap) {
  if (m == word.length()) {
    return 1;
  }

  int result = 0;
  for (String nextString : prefixMap.getOrDefault(word.charAt(m), emptyList())) {
    if (m + nextString.length() > word.length()) {
      break;
    }

    // Start at m+1, because you already know they match at m.
    if (word.regionMatches(m + 1, nextString, 1, nextString.length()-1)) {
      // This is a potential match!
      // Make a recursive call.
      result += method(word, m + nextString.length(), prefixMap);
    }
  }
  return result;
}

（*）这可能会构造Character的新实例，因为word.charAt(m)的装箱：缓存实例保证仅用于0-127范围内的字符。有很多方法可以解决这个问题，但它们只会让代码变得混乱