An algorithm for removing a character from a word so that the given word is still a word in the dictionary

Question

Here is the script. Given the word, remove one character from the word at each step so that the shortened word is still a word in the dictionary. Continue until the characters remain.

Here's the catch: You need to delete the correct character, for example. in a word, there can be two possible characters that can be deleted, and both can cause the abbreviated word to be a real word, but at a later stage you can reduce it to the end, that is, there are no characters left until the other can hang the receiver.

Example:

• planet
• Plant
• pant
• pan
• element
• but

OR

• planet
• Plane
• band
• Impossible further, suppose lan is not a word. hope you have an idea.

Please see my code, im using recursion, but would like to know if there are more efficient solutions to do the same.

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

Run the BFS algorithm. If you have several characters that you can delete, delete them individually and put them in the priority queue, if you want to restore the path, save the pointer to the parent (source word from which you created this word by deleting the character) words in node itslef . And when you delete all characters, complete and restore the path, or if there is no valid path, you will have an empty priority queue

Answer 2

I used Porter Stemming in several projects - this, of course, will only help you trim the end of a word.

The Porter Restriction Algorithm (or Porter-Stem) is a process for removing commonly used morphological and inflectional endings from words in English. Its main use is part of the process of normalizing the term, which is usually done when setting up information search engines.

Reprint in MF Porter, 1980, Algorithm for Removing the Suffix, Program, 14 (3) pp. 130-137 .

Martin even has an affordable version of Java on his site.

Answer 3

Here you go. The mash method will find a solution (a list of dictionary words) for any given string, using the dictionary passed to the constructor. If there is no solution (ends with one alphabetic word), the method returns null. If you are interested in all partial solutions (ending before receiving a single-letter word), you should adjust the algorithm a bit.

A dictionary is considered a set of strings in uppercase. Of course, you can use your own class / interface.

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

Example:

 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 4

OK, this is not Java, just JavaScript, but you can probably convert it:

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 5

Make a trie (or suffix tree ) with the given characters in the word (without repetition) and check each trie subtree with the dictionary. This should help you.

For reference, visit

• Suffix tree
• Trie

Answer 6

Here is an algorithm that uses deep search. Given the word, you check if it is valid (in the dictionary). If its value is valid, remove one character from the row in each index and recursively check that the word "chopped" is back again. If the broken word is invalid at any time, you are mistaken and return to the previous step.

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