从单词中删除字符的算法,使得缩小的单词仍然是字典中的单词

Question

这是一个场景,给定一个单词从每个步骤中的单词中删除单个字符,使得缩小的单词仍然是字典中的单词.继续,直到没有人物离开.

这是一个问题:你需要删除正确的字符,例如.总之,可能有两个可能被移除的字符,两者都可能导致缩小的单词成为有效单词,但是在稍后阶段,可能会减少到最后,即没有剩下的字符,而另一个可能挂断.

例:

• 行星
• 厂
• 喘气
• 泛
• 一个
• 一个

要么

• 行星
• 平面
• 车道
• 不可能进一步,假设局域网不是一个词.希望你有这个主意.

请参阅我的代码,我使用递归,但想知道是否有更好的有效解决方案来做同样的事情.

public class isMashable
{

  static void initiate(String s)
  {
    mash("", s);
  }

  static void mash(String prefix, String s)
  {
    int N = s.length();
    String subs = "";

    if (!((s.trim()).equals("")))
      System.out.println(s);

    for (int i = 0 ; i < N ; i++)
    {
      subs = s.substring(0, i) + s.substring(i+1, N);
      if (subs.equals("abc")||subs.equals("bc")||subs.equals("c")||subs.equals("a")) // check in dictionary here
        mash("" + s.charAt(i), subs);
    }
  }

  public static void main(String[] args)
  {
    String s = "abc";
    initiate(s);
  }
}

Answer 1

运行 BFS 算法。如果您有多个可以删除的字符，请单独删除它们并放入优先级队列中，如果您想回溯路径，请将指针保留到父级（通过删除字符创建该单词的原始单词） ）节点本身中的单词。当你删除所有字符，终止并回溯路径，或者如果没有有效的方法时，你将有一个空的优先级队列