Algoritmo per rimuovere un carattere da una parola tale che la parola ridotta sia ancora una parola nel dizionario

Question

Ecco lo scenario, Dato una parola rimuovere un singolo carattere da una parola in ogni passaggio in modo tale che la parola ridotta sia ancora una parola in dizionario. Continua finché non vengono lasciati caratteri.

Ecco il codice: È necessario rimuovere il carattere corretto, ad es. in una parola possono esserci due possibili caratteri che possono essere rimossi e entrambi possono far sì che la parola ridotta sia una parola valida, ma in una fase successiva si può ridurre alla fine, cioè non rimangono caratteri mentre l'altro può riagganciare.

Esempio:

• pianeta
• pianta
• mutanda
• vaschetta
• un
• un

O

• pianeta
• piano
• corsia
• non è possibile ulteriormente, supponiamo lan non è una parola. spero che tu abbia avuto l'idea.

Si prega di consultare il mio codice, im utilizzando la ricorsione, ma vorrei sapere se ci sono soluzioni efficienti migliori per fare lo stesso.

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

Eseguire un algoritmo BFS. Se hai più di un carattere che puoi rimuovere, rimuovili individualmente e inserisci una coda di priorità, se vuoi tracciare il percorso, tieni il puntatore al genitore (la parola originale da cui hai creato questa parola rimuovendo un carattere) della parola nel nodo itslef. E quando rimuovi tutti i caratteri, termina e ritraccia il percorso, o se non esiste un modo valido, avrai una coda di priorità vuota

Answer 2

OK, non è Java, solo JavaScript, ma probabilmente puoi trasformarlo:

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

Answer 3

ho usato Porter Stemming in un paio di progetti - che sarà ovviamente solo aiutare a tagliare fuori la fine della parola.

L'algoritmo derivante Porter (o ‘Porter Stemmer’) è un processo per rimuovere il più comune terminazioni morfologiche e flessionali da parole in inglese. Il suo uso principale è come parte di un processo di normalizzazione del termine che viene solitamente eseguito durante l'impostazione dei sistemi di recupero informazioni.

Una ristampa è scattata nel M.F. Porter, 1980, An algorithm for suffix stripping, Program, 14(3) pp 130−137.

Martin ha anche un Java version available sul suo sito.

Answer 4

Creare un trie (o suffix tree) con i caratteri specificati nella parola (nessuna ripetizione consentita) e controllare ogni sottostruttura di trie con il dizionario. Questo dovrebbe aiutarti.

Per Visita riferimento

• Suffix tree
• Trie

Answer 5

Qui si va. Il metodo mash troverà una soluzione (elenco di parole del dizionario) per ogni dato String usando un dizionario passato al costruttore. Se non c'è soluzione (che termina con una parola di una sola lettera), il metodo restituirà null. Se sei interessato a tutte le soluzioni parziali (che terminano prima di arrivare a una parola di una sola lettera), dovresti modificare un po 'l'algoritmo.

Si presume che il dizionario sia un insieme di stringhe maiuscole. Potresti ovviamente usare la tua classe/interfaccia.

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

} 

Esempio:

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")); 

Answer 6

Ecco un algoritmo che utilizza ricerca in profondità. Data una parola, si controlla se è valida (nel dizionario). Se è valido, rimuovi un carattere dalla stringa in ciascun indice e controlla in modo ricorsivo che la parola "tagliata" sia di nuovo valida. Se la parola tagliata non è valida in alcun punto, si è nel percorso sbagliato e si ritorna al passaggio precedente.

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


    } 

}