Databases
StackOverflow2013
Postsdbo
POjava string permutations and combinations lookup
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POjava string permutations and combinations lookup
    text
    copied!<p>I'm writing an <em>Android</em> word app. My code includes a method that would find all combinations of the string and the substrings of a 7 letter string with a minimum of length 3. Then compare all available combination to every word in the dictionary to find all the valid words. I'm using a recursive method. Here's the code.</p> <pre><code>// Gets all the permutations of a string. void permuteString(String beginningString, String endingString) { if (endingString.length() &lt;= 1){ if((Arrays.binarySearch(mDictionary, beginningString.toLowerCase() + endingString.toLowerCase())) &gt;= 0){ mWordSet.add(beginningString + endingString); } } else for (int i = 0; i &lt; endingString.length(); i++) { String newString = endingString.substring(0, i) + endingString.substring(i + 1); permuteString(beginningString + endingString.charAt(i), newString); } } // Get the combinations of the sub-strings. Minimum 3 letter combinations void subStrings(String s){ String newString = ""; if(s.length() &gt; 3){ for(int x = 0; x &lt; s.length(); x++){ newString = removeCharAt(x, s); permuteString("", newString); subStrings(newString); } } } </code></pre> <p>The above code runs fine but when I installed it on my Nexus s I realized that it runs a bit too slow. It takes a few seconds to complete. About 3 or 4 seconds which is unacceptable. Now I've played some word games on my phone and they compute all the combinations of a string instantly which makes me believe that my algorithm is not very efficient and it can be improved. Can anyone help?</p> <hr> <pre><code>public class TrieNode { TrieNode a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z; TrieNode[] children = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z}; private ArrayList&lt;String&gt; words = new ArrayList&lt;String&gt;(); public void addWord(String word){ words.add(word); } public ArrayList&lt;String&gt; getWords(){ return words; } } </code></pre> <hr> <pre><code>public class Trie { static String myWord; static String myLetters = "afinnrty"; static char[] myChars; static Sort sort; static TrieNode myNode = new TrieNode(); static TrieNode currentNode; static int y = 0; static ArrayList&lt;String&gt; availableWords = new ArrayList&lt;String&gt;(); public static void main(String[] args) { readWords(); getPermutations(); } public static void getPermutations(){ currentNode = myNode; for(int x = 0; x &lt; myLetters.length(); x++){ if(currentNode.children[myLetters.charAt(x) - 'a'] != null){ //availableWords.addAll(currentNode.getWords()); currentNode = currentNode.children[myLetters.charAt(x) - 'a']; System.out.println(currentNode.getWords() + "" + myLetters.charAt(x)); } } //System.out.println(availableWords); } public static void readWords(){ try { BufferedReader in = new BufferedReader(new FileReader("c://scrabbledictionary.txt")); String str; while ((str = in.readLine()) != null) { myWord = str; myChars = str.toCharArray(); sort = new Sort(myChars); insert(myNode, myChars, 0); } in.close(); } catch (IOException e) { } } public static void insert(TrieNode node, char[] myChars, int x){ if(x &gt;= myChars.length){ node.addWord(myWord); //System.out.println(node.getWords()+""+y); y++; return; } if(node.children[myChars[x]-'a'] == null){ insert(node.children[myChars[x]-'a'] = new TrieNode(), myChars, x=x+1); }else{ insert(node.children[myChars[x]-'a'], myChars, x=x+1); } } } </code></pre>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload