1

我刚刚在网上遇到了这个有趣的问题，对于如何在它上面取得进展感到很困惑。

Write a function that finds all the different ways you can split up a word into a
concatenation of two other words.

这是使用后缀树的东西吗？

我不是在寻找代码，只是在概念上推进这一点。

4

3 回答 3

6

一些伪代码：

   foreach place you can split the word:
    split the word.
    check if both sides are valid words.
于 2012-06-15T17:27:21.593 回答
2

如果您正在寻找一个好的答案，请告诉我们您对有效词的定义。

假设一个单词是一个在字母表上定义的字符串，并且长度大于零。您可以使用后缀树。

下面是一个简化的算法，只需要 O(n) 时间。

Convert the word into a character array.

Traverse through the length of the array and for each i just take two strings (0 to i) and 
(i+1     to    length of the array-1).

请记住涵盖基本条件，例如长度大于零。

于 2012-06-15T17:32:04.060 回答
-2

当且仅当此条件成立时，执行此操作的不同方法的总数可以大于一种：

-> 两个单词之一必须是其他单词的倍数。例如：“abcd”和“abcdabcd”。使用这两个词，你可以用许多不同的方式组成字符串“abcdabcdabcdabcd”。

所以首先检查这个条件。

然后检查是否可以以任何方式从这两个单词中写入字符串。那么简单的数学应该会给你答案

于 2018-07-12T13:58:59.863 回答