java - 给定 SuperString 是否可以使用给定子字符串的任意组合

Question

假设我们有输入子字符串——“john”“mathew”“carl”我们必须找到超级字符串可以使用这些子字符串形成或不输出应该是“yes”或“no”

例如-

子字符串-约翰·马纽·卡尔

super String 1- johncarl (john 和 carl 都在子字符串中) 输出-是

super String 2-carlmathewjohn(john,mathew and carl all are in sub strings) 输出-是

super String 3-mohammedjohn（子字符串中没有穆罕默德）输出-否

超级字符串 4-johnadbul（子字符串中没有 abdul）输出-否

super String 5-john 输出是

super String 6-carlmathewjohnrohit（子字符串中没有 rohit）输出 no

标签： javaalgorithmcombinatorics

Answer 1

您可以使用 Map 来完成此操作，通常只需一次通过。

字符串是否以任何可用单词开头，如果不是，则停止。

如果是，则删除该单词并继续，直到字符串被使用。或者你必须停下来。唯一的复杂性是当这里有多个可能的单词要使用时，在这种情况下你需要全部尝试。为此，您需要递归和一些回溯。