10

这是场景，给定一个单词，在每个步骤中从单词中删除一个字符，这样减少的单词仍然是字典中的单词。继续直到没有字符。

这是一个问题：您需要删除正确的字符，例如。在一个单词中可能有两个可能的字符可以被删除，并且两者都可能导致缩减后的单词成为有效单词，但在稍后阶段，一个可能会缩减到最后，即没有字符留下，而另一个可能挂断。

例子：

  • 行星
  • 植物
  • 喘气
  • 平底锅
  • 一个
  • 一个

或者

  • 行星
  • 飞机
  • 车道
  • 不可能进一步，假设 lan 不是一个词。希望你明白了。

请查看我的代码，我使用递归，但想知道是否有更有效的解决方案来做同样的事情。

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

6 回答 6

2

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

于 2012-06-28T06:33:36.977 回答
1

我在几个项目中使用了Porter Stemming——这当然只会帮助你修剪单词的结尾。

Porter 词干算法（或“Porter stemmer”）是一种从英语单词中去除常见的形态和屈折词尾的过程。它的主要用途是作为通常在设置信息检索系统时完成的术语规范化过程的一部分。

MF Porter, 1980, An algorithm for suffix stripping, Program, 14(3) pp 130−137重印。

Martin 甚至在他的网站上提供了 Java 版本。

于 2012-06-28T07:54:07.593 回答
1

干得好。mash 方法将使用传递给构造函数的字典为任何给定字符串找到解决方案（字典单词列表）。如果没有解决方案（以一个字母单词结尾），该方法将返回 null。如果您对所有部分解决方案感兴趣（在到达一个字母单词之前结束），您应该稍微调整一下算法。

字典被假定为一组大写字符串。您当然可以改用自己的类/接口。

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class WordMash {

    private final Set<String> dictionary;

    public WordMash(Set<String> dictionary) {
        if (dictionary == null) throw new IllegalArgumentException("dictionary == null");
        this.dictionary = dictionary;
    }

    public List<String> mash(String word) {
        return recursiveMash(new ArrayList<String>(), word.toUpperCase());
    }

    private List<String> recursiveMash(ArrayList<String> wordStack, String proposedWord) {
        if (!dictionary.contains(proposedWord)) {
            return null;
        }
        wordStack.add(proposedWord);

        if (proposedWord.length() == 1) {
            return wordStack;
        }

        for (int i = 0; i < proposedWord.length(); i++) {
            String nextProposedWord = 
                proposedWord.substring(0, i) + proposedWord.substring(i + 1, proposedWord.length());    
            List<String> finalStack = recursiveMash(wordStack, nextProposedWord);
            if (finalStack != null) return finalStack;
        }

        return null;
    }

}

例子：

Set<String> dictionary = new HashSet<String>(Arrays.asList(
        "A", "AFRICA", "AN", "LANE", "PAN", "PANT", "PLANET", "PLANT"
));
WordMash mash = new WordMash(dictionary);

System.out.println(mash.mash("planet"));
System.out.println(mash.mash("pant"));


System.out.println(mash.mash("foo"));
System.out.println(mash.mash("lane"));
System.out.println(mash.mash("africa"));
于 2012-06-28T09:29:56.937 回答
1

这是一种使用深度优先搜索的算法。给定一个单词，您检查它是否有效（在字典中）。如果它有效，则从每个索引处的字符串中删除一个字符，并递归地检查“chopped”单词是否再次有效。如果切碎的单词在任何时候都无效，则说明您走错路并返回上一步。

import java.util.HashSet;
import java.util.Set;

public class RemoveOneCharacter {
    static Set<String> dict = new HashSet<String>();

    public static boolean remove(String word){
        if(word.length() == 1)
            return true;

        if(!dict.contains(word))
            return false;

        for(int i=0;i<word.length();i++){
            String choppedWord = removeCharAt(word,i);
            boolean result = remove(choppedWord);
            if(result)
                return true;
        }
        return false;
    }

    public static String removeCharAt(String str, Integer n) {
        String f = str.substring(0, n);
        String b = str.substring(n+1, str.length());
        return f + b;
    }

    public static void main(String args[]){
        dict.add("heat");
        dict.add("eat");
        dict.add("at");
        dict.add("a");

        dict.add("planets");
        dict.add("planet");
        dict.add("plant");
        dict.add("plane");
        dict.add("lane");
        dict.add("plants");
        dict.add("pant");
        dict.add("pants");
        dict.add("ant");
        dict.add("ants");
        dict.add("an");


        dict.add("clean");
        dict.add("lean");
        dict.add("clan");
        dict.add("can");

        dict.add("why");

        String input = "heat";
        System.out.println("result(heat) " + remove(input));
        input = "planet";
        System.out.println("result(planet) " + remove(input));
        input = "planets";
        System.out.println("result(planets) " + remove(input));
        input = "clean";
        System.out.println("result(clean) " + remove(input));
        input = "why";
        System.out.println("result(why) " + remove(input));
        input = "name";
        System.out.println("result(name) " + remove(input));


    }

}
于 2016-10-16T02:07:33.760 回答
0

用单词中的给定字符创建一个trie（或suffix tree）（不允许重复），并用字典检查 trie 的每个子树。这应该可以帮助你。

供参考访问

于 2012-06-28T08:24:39.540 回答
0

好吧，它不是 Java，只是 JavaScript，但也许你可以转换它：

http://jsfiddle.net/BA8PJ/

function subWord( w, p, wrapL, wrapR ){
  return w.substr(0,p)
      + ( wrapL ? (wrapL + w.substr(p,1) + wrapR ):'')
      + w.substr(p+1);
}

// wa = word array:         ['apple','banana']
// wo = word object/lookup: {'apple':true,'banana':true}
function initLookup(){
  window.wo = {};
  for(var i=0; i < wa.length; i++) wo[ wa[i] ] = true;
}



function initialRandomWords(){
  // choose some random initial words
  var level0 = [];
  for(var i=0; i < 100; i++){
    var w = wa[ Math.floor(Math.random()*wa.length) ];
    level0.push({ word: w, parentIndex:null, pos:null, leaf:true });
  }
  return level0;
}



function generateLevels( levels ){
  while(true){
    var nl = genNextLevel( levels[ levels.length-1 ]);
    if( ! nl ) break;
    levels.push( nl );
  }
}

function genNextLevel( P ){ // P: prev/parent level
  var N = [];               // N: next level
  var len = 0;
  for( var pi = 0; pi < P.length; pi ++ ){
    pw = P[ pi ].word; // pw: parent word
    for( var cp = 0; cp < pw.length; cp++ ){ // cp: char pos
      var cw = subWord( pw, cp ); // cw: child word
      if( wo[cw] ){
        len++;
        P[ pi ].leaf = false;
        N.push({ word: cw, parentIndex:pi, pos:cp, leaf:true });
      }
    }
  }
  return len ? N : null;
}



function getWordTraces( levels ){
  var rows = [];
  for( var li = levels.length-1; li >= 0; li-- ){
    var level = levels[ li ];
    for( var i = 0; i < level.length; i++ ){
      if( ! level[ i ].leaf ) continue;
      var trace = traceWord( li, i );
      if( trace.length < 2 ) continue;
      rows.push( trace );
    }
  }
  return rows;
}

function traceWord( li, i ){
  var r = [];
  while(true){
    var o = levels[ li ][ i ];
    r.unshift( o );
    i = o.parentIndex;
    if( !i ) break;
    li--;
    if( li < 0 ) break;
  };
  return r;
}



function compareTraces( aa, bb ){
  var a = aa[0].word, b = bb[0].word;
  if( a == b ){
    if( aa.length < bb.length ) return -1;
    if( aa.length > bb.length ) return +1;
  }

  var len = Math.min( aa.length, bb.length )
  for( var i = 0; i < len; i++ ){
    var a = aa[i].word, b = bb[i].word;
    if( a < b ) return +1;
    if( a > b ) return -1;
  }

  if( aa.length < bb.length ) return -1;
  if( aa.length > bb.length ) return +1;

  return 0;
}


function prettyPrintTraces( rows ){
  var prevFirstWord = null;
  for( var ri = rows.length-1; ri >= 0; ri-- ){
    var row = rows[ ri ];

    if(  prevFirstWord != row[0].word  ){
      if( prevFirstWord ) $('body').append('<div class="sep"/>');
      prevFirstWord = row[0].word;
    }

    var $row = $('<div class="row"/>');
    for( var i = 0; i < row.length; i++ ){

      var w = row[i].word;
      var c = row[i+1];
      if( c )  w = subWord( w, c.pos, '<span class="cut">', '</span>');

      var $word = $('<div class="word"></div>').html( w ).toggleClass('last-word', w.length < 2 );
      $row.append( $word );
    }
    $('body').append( $row );
  }
};

function main(){
  initLookup();

  window.levels = [ initialRandomWords() ];

  generateLevels( levels );

  rows = getWordTraces( levels );

  rows.sort( compareTraces );

  prettyPrintTraces( rows );
}
于 2012-06-28T07:40:35.250 回答