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

Question

Given 是一个字符串 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” + “低”

2:“sta” + “ck” + “ove” + “rf” + “低”

如果 word 相对较小(<15 个字符)，我的程序实现只会在所需的时间内终止。然而，正如我之前提到的，程序的运行时间限制是 6 秒，并且它应该能够处理非常大的 word 字符串(>1000 个字符)。 Here是一个大输入的例子。

这是我的代码:

1)实际方法:

输入:一个字符串单词和一个字符串[] 书

输出:仅使用书中的字符串可以编写单词的方式数

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) allSubstrings():

输入:字符串输入

输出:列表的列表，每个列表包含加起来为输入的子字符串的组合

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;
}

3.) sumup():

输入:字符串列表输入和字符串预期

输出:如果输入中的元素加起来达到预期，则为 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 中做错了什么:我没有使用内存，所以我重做了很多不必要的工作。

考虑一个书籍数组 {"a", "aa", "aaa"} ，以及目标词 "aaa" 。有四种方法可以构建此目标:

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

我之前的尝试会分别遍历所有四个。但相反，人们可以观察到:

• 有 1 种方法可以构造 "a"
• 您可以构造"aa"有两种方式，要么 "a" + "a"或使用"aa"直接。
• 您可以构造"aaa"通过使用 "aaa"直接(1 种方式)；或"aa" + "a" (有两种方法，因为有两种方法可以构造 "aa" )；或"a" + "aa" (1 种方式)。

请注意，这里的第三步仅将一个附加字符串添加到先前构造的字符串中，为此我们知道它可以构造的方式的数量。

这表明，如果我们计算前缀 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 启动时间。

---

编辑:事实上，特里树并不是必需的。您可以简单地将“Walk the trie”循环替换为:

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

它的执行速度较慢，但​​仍然比 6 秒快得多:

2217093120

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