10

シナリオは次のとおりです。単語が与えられた場合、すべてのステップで単語から1文字を削除し、削減された単語が辞書内の単語のままになるようにします。文字がなくなるまで続けます。

キャッチは次のとおりです。たとえば、適切な文字を削除する必要があります。単語では、削除できる2つの文字があり、どちらも縮小された単語が有効な単語になる可能性がありますが、後の段階で一方が最後まで縮小される可能性があります。つまり、文字が残っていないのにもう一方がハングアップする可能性があります。

例：

  • 星
  • 工場
  • パンツ
  • パン
  • と
  • a

また

  • 星
  • 飛行機
  • LANE
  • これ以上不可能ですが、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 アルゴリズムを実行します。削除できる文字が複数ある場合は、それらを個別に削除して優先キューに入れます。パスをたどりたい場合は、親 (文字を削除してこの単語を作成した元の単語) へのポインターを保持します。 ) ノード自体の単語の。そして、すべての文字を削除すると、パスを終了して再トレースするか、有効な方法がない場合は、優先キューが空になります

于 2012-06-28T06:33:36.977 に答える
1

どうぞ。mash-methodは、コンストラクターに渡された辞書を使用して、任意の文字列の解決策（辞書の単語のリスト）を見つけます。解決策がない場合（1文字の単語で終わる）、メソッドはnullを返します。すべての部分的な解決策（1文字の単語に到達する前に終了する）に関心がある場合は、アルゴリズムを少し調整する必要があります。

辞書は大文字の文字列のセットであると想定されています。もちろん、代わりに独自のクラス/インターフェースを使用することもできます。

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

私はいくつかのプロジェクトでPorter Stemmingを使用しましたが、これはもちろん、単語の末尾を削除するのに役立つだけです。

ポーター ステミング アルゴリズム (または「ポーター ステマー」) は、英語の単語から一般的な形態語尾と屈折語尾を削除するプロセスです。その主な用途は、情報検索システムをセットアップするときに通常行われる用語の正規化プロセスの一部としてです。

MF Porter、1980、An algorithm for suffix stripping、Program、14(3) pp 130-137で再版が行われました。

Martin のサイトには、Java バージョンも用意されています。

于 2012-06-28T07:54:07.593 に答える
0

単語内の指定された文字でtrie(またはsuffix tree) を作成し (繰り返しは許可されません)、トライの各サブツリーを辞書で確認します。これはあなたを助けるはずです。

参考にご覧ください

于 2012-06-28T08:24:39.540 に答える
0

OK、これは 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 に答える