在最近的一次面试中,我被要求提出以下问题的解决方案:给定一个字符串 s(不含空格)和一个字典,返回由字典组成该字符串的单词。例如,s=peachpie,dic={peach,pie},结果为{peach,pie}。现在请问:如果 s 可以由字典中的单词组成,则返回 yes,否则返回 no。我的解决方案是使用回溯算法(用 Java 编写)。
public static boolean words(String s, Set<String> dictionary)
{
if ("".equals(s))
return true;
for (int i=0; i <= s.length(); i++)
{
String pre = prefix(s,i); // returns s[0..i-1]
String suf = suffix(s,i); // returns s[i..s.len]
if (dictionary.contains(pre) && words(suf, dictionary))
return true;
}
return false;
}
public static void main(String[] args) {
Set<String> dic = new HashSet<String>();
dic.add("peach");
dic.add("pie");
dic.add("1");
System.out.println(words("peachpie1", dic)); // true
System.out.println(words("peachpie2", dic)); // false
}
这个解决方案的时间复杂度是什么? 我在for循环中进行递归调用,但只针对字典中存在的前缀。
有什么想法吗?
applepie
的结果显然是错误的。看一下问题的定义:如果s可以由字典中的单词组成,则返回yes。apple
不在字典中。 - Itsik