给定六个字母找到不同长度的单词

#1 楼

char[] prefix= new char[6];
for(int l1 = 0; l1 < 6; l1++){
    prefix[0]=anagramCharacters[l1];
    for(int l2 = 0; l2 < 6; l2++)
        if(l2 != l1){
        prefix[1]=anagramCharacters[l2];

List<String> createAnagrams(char[] chars, SortedSet<String> sortedDictionary){
    List<String result = new ArrayList<String>();
    fillListWithAnagrams(result, sortedDictionary, chars, 0);
    return result;
}

void fillListWithAnagrams(List<String> result, SortedSet<String> sortedDictionary, char[] chars, int charIndex){
    if(charIndex>=3){
       String resultString = new String(chars,0,charIndex);
       if(sortedDictionary.contains(resultString);
           list.add(resultString);
    }

    if(charIndex>=chars.length)
       return;//end of the line

    for(int i = charIndex;i<chars.length;i++){
        char t = chars[i];
        chars[i] = chars[charIndex];
        chars[charIndex] = t;

        fillListWithAnagrams(list, sortedDictionary, chars, charIndex+1);

        // revert the char array for the next step
        //t=chars[charIndex];
        chars[charIndex] = chars[i];
        chars[i] = t;
    }

}

#2 楼

if(sortedDictionary.contains(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]))
     anagram_words.add(""+anagramCharacters[l1]+anagramCharacters[l2]+anagramCharacters[l3]);

private void addWord(char... chars) {
    String string = "";
    for (char ch : chars) string += ch; // Create a strings of the chars
    if (sortedDictionary.contains(string))
        anagram_words.add(string);
}

if (sortedDictionary.contains(....)) anagram_words.add(...)

addWord(anagramCharacters[l1], anagramCharacters[l2], anagramCharacters[l3]);

if(l4 != l1 && l4 != l2 && l4 != l3)

if(letters[3] != letters[0] && letters[3] != letters[1] && letters[3] != letters[2])

if(letters[3] != letters[0] && letters[3] != letters[1] && letters[3] != letters[2])

private boolean lastLetterDifferent(int index) {
    for (int i = 0; i < index; i++) {
        if (letters[i] == letters[index]) return false;
    }
    return true;
}

private void addWord(int numberOfChars) {
    String string = "";
    for (int i = 0; i < numberOfChars; i++) string += anagramCharacters[letters[i]]; // Create a strings of the chars
    if (sortedDictionary.contains(string))
        anagram_words.add(string);
}

for(letters[0] = 0; letters[0] < 6; letters[0]++){
    for(letters[1] = 0; letters[1] < 6; letters[1]++) {
        if(lastLetterDifferent(1)) {
            for(letters[2] = 0; letters[2] < 6; letters[2]++) {
                if(letters[2] != letters[0] && letters[2] != letters[1]) {
                    addWord(3);
                    for(letters[3] = 0; letters[3] < 6; letters[3]++) {
                        if (lastLetterDifferent(3)) {
                            addWord(4);
                            for(letters[4] = 0; letters[4] < 6; letters[4]++){
                                if (lastLetterDifferent(4)) {
                                    addWord(5);
                                    for(letters[5] = 0; letters[5] < 6; letters[5]++){
                                        if (lastLetterDifferent(5)) {
                                            addWord(6);
                                        }
                                    }   
                                }
                            }   
                        }
                    }
                }
            }
        }
    }
}

#3 楼

private static final void checkWord(char[] chars, char[]current, int len, List<String> results) {
    if (len == chars.length) {
        final String result = new String(current);
        if (sortedDictionary.contains(result)) {
             results.add(result);
        }
    } else {
        // get the next combination for what is left in the chars
        for int (i = xx; i < yy; i++) {
            current[len] = .... // next char to try
            checkWord(chars, current, len+1 results);
        }
    }
}

import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.Collection;
import java.util.Set;
import java.util.TreeSet;


public class Words {

    /**
     * Calculate all possible ways to permute data sets of up to 'max' values...
     * <p>
     * The result is a multi-dimensional array, with result[2] being the ways to
     * permute 2-sized data sets ([1,2],[2,1]), and result[3] the way to permute 3-sized sets:
     * ([1,2,3],[1,3,2],[2,3,1],[2,1,3],[3,1,2],[3,2,1]),
     * etc.
     * 
     * @param max the largest set to calculate permutations for.
     * @return the possible ways to permute sets of values up to max values in size
     */
    private static final int[][][] permutations(int max) {
        int[][][] ret = new int[max + 1][][];
        ret[0] = new int[0][];
        ret[1] = new int[1][1];
        for (int i = 2; i <= max; i++) {
            ret[i] = new int[factorial(i)][];
            int[] remaining = new int[i];
            for (int j = 0; j < i; j++) {
                remaining[j] = j;
            }
            permutationGen(i, ret[i], 0, new int[0], remaining);
        }
        return ret;
    }

    /**
     * calculate the factorial of a number.
     * The factorial is the number of permutations available for a given set of values.
     * @param n the number to calculate
     * @return the factorial (n!)
     */
    private static int factorial(int n) {
        int ret = n;
        while (--n > 1) {
            ret *= n;
        }
        return ret;
    }

    /**
     * Recursive function to calculate the permutations of a dataset of a specified size.
     * @param size The number of elements to calculate the permutations for
     * @param store The place to store the permutations
     * @param nextstore the next location to save values in the store
     * @param used the positions that have been used in already in building the current permutations
     * @param remaining the remaining positions that need to be used.
     * @return the index of the next permutation to save
     */
    private static int permutationGen(final int size, final int[][] store, int nextstore, final int[] used, final int[] remaining) {

        if (used.length == size) {
            store[nextstore] = used;
            return nextstore + 1;
        }
        int [] nremain = Arrays.copyOfRange(remaining, 1, remaining.length);
        for (int r = 0; r < remaining.length; r++) {
            int [] nused = Arrays.copyOf(used, used.length + 1);
            if (r > 0) {
                nremain[r - 1] = remaining[r - 1];
            }
            nused[used.length] = remaining[r];
            nextstore = permutationGen(size, store, nextstore, nused, nremain);

        }
        return nextstore; 
    }

    /**
     * Recursive combination function. It determines all possible combinations for a set of data, and for
     * each combination it also then runs through all permutations.
     * With the permutations it checks to see whether the word created by that combination/permutation is
     * a real word, and if it is, it adds it to the anagrams solution set.
     * @param words the valid words
     * @param chars the actual characters we can use to anagram
     * @param charpos the position in the chars that we are currently processing
     * @param current the letters we currently have in our combination already.
     * @param currentlen the number of letters in current that are valid.
     * @param permutes the possible permutations for different-sized datasets.
     * @param anagrams where to store the valid words when we find them.
     */
    private static void checkCombinations(final String[] words, final char[] chars, final int charpos,
            final char[] current, final int currentlen, final int[][][] permutes, final Collection<String> anagrams) {

        if (currentlen >= current.length) {
            return;
        }

        for (int i = charpos; i < chars.length; i++) {
            current[currentlen] = chars[i];

            // This is th recursive function to calculate combinations.
            checkCombinations(words, chars, i + 1, current, currentlen + 1, permutes, anagrams);

            // for each combination, run through all the permutations.
            char[] strchr = new char[currentlen + 1];
            for (int[] perm : permutes[currentlen + 1]) {
                for (int j = 0; j <= currentlen; j++) {
                    strchr[j] = current[perm[j]];
                }
                String word = new String(strchr);
                if (Arrays.binarySearch(words, word) >= 0) {
                    anagrams.add(word);
                }
            }

        }

    }

    public static void main(String[] args) throws IOException {
        System.out.println("Reading Linux words file (typically /usr/share/dict/linux.words)");
        String words[] = Files.readAllLines(Paths.get("linux.words"), StandardCharsets.UTF_8).toArray(new String[0]);
        System.out.println("Convert all to lowercase");
        for (int i = 0; i < words.length; i++) {
            words[i] = words[i].toLowerCase();
        }
        System.out.println("Sort all words (" + words.length + ")");
        Arrays.sort(words);
        char[] chars = "abcdef".toLowerCase().toCharArray();

        Set<String> anagrams = new TreeSet<>();

        System.out.println("building permutations for " + chars.length + " sizes");
        int[][][] permutations = permutations(chars.length);

        System.out.println("calculating combinations and permutations of '" + new String(chars) + "'.");
        long time = System.nanoTime();
        checkCombinations(words, chars, 0, new char[chars.length], 0, permutations, anagrams);
        System.out.printf("Found %d words.... in %.3fms\n", anagrams.size(), (System.nanoTime() - time) / 1000000.0);
        for (String s : anagrams) {
            System.out.println(s);
        }

    }

}

#4 楼

public static List<String> findWords(char[] letters, List<String> sortedDictionary) {
    letters = Arrays.copyOf(letters, letters.length);
    Arrays.sort(letters);
    char[] buf = new char[letters.length];

    List<String> anagramWords = new ArrayList<String>();
    for (String word : sortedDictionary) {
        int len = word.length();
        if (len < 3 || len > letters.length) {
            continue;
        }
        word.getChars(0, len, buf, 0);
        Arrays.sort(buf, 0, len);
        if (isSubsequence(buf, len, letters)) {
            anagramWords.add(word);
        }
    }
    return anagramWords;
}

private static boolean isSubsequence(char[] needle, int needleLen, char[] haystack) {
    for (int n = 0, h = 0; n < needleLen && h < haystack.length; n++, h++) {
        while (needle[n] > haystack[h]) {
            h++;
            if (h >= haystack.length) {
                return false;
            }
        }
        if (needle[n] < haystack[h]) {
            return false;
        }
        assert needle[n] == haystack[h];
    }
    return true;
}

#5 楼

public abstract class PermutationsIterator implements Iterator<List<Integer>> {
  // Length of the lists required.
  protected final int length;
  // The working list.
  protected final List<Integer> indexes;
  // The next to deliver.
  private List<Integer> next = null;

  public PermutationsIterator(int length) {
    this.length = length;
    indexes = new ArrayList<>(length);
    for (int i = 0; i < length; i++) {
      indexes.add(i);
    }
    // Deliver the base one first.
    this.next = Collections.unmodifiableList(indexes);
  }

  // Return true if a next was available.
  protected abstract boolean getNext();

  @Override
  public boolean hasNext() {
    if (next == null) {
      // Is there one?
      if ( getNext() ) {
          // That's next!
          next = Collections.unmodifiableList(indexes);
      }
    }
    return next != null;
  }

  @Override
  public List<Integer> next() {
    List<Integer> n = hasNext() ? next : null;
    next = null;
    return n;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException("Cannot remove from permutations");
  }

}

public class LexicographicPermutationsIterator extends PermutationsIterator implements Iterator<List<Integer>> {

  public LexicographicPermutationsIterator(int length) {
    super(length);
  }

  @Override
  protected boolean getNext() {
    boolean got = false;
    // Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
    int k = -1;
    for (int i = 0; i < length - 1; i++) {
      if (indexes.get(i) < indexes.get(i + 1)) {
        k = i;
      }
    }
    if (k >= 0) {
      int ak = indexes.get(k);
      // Find the largest index l such that a[k] < a[l].
      int l = k + 1;
      for (int i = 0; i < length; i++) {
        if (ak < indexes.get(i)) {
          l = i;
        }
      }
      // Swap the value of a[k] with that of a[l].
      Collections.swap(indexes, k, l);
      // Reverse the sequence from a[k + 1] up to and including the final element a[n].
      Collections.reverse(indexes.subList(k + 1, indexes.size()));
      // We got one.
      got = true;
    }
    return got;
  }

}

#6 楼

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class WordsSearchMain {
    public static void main(String... ignored) throws IOException {
        Dictionary dict = new Dictionary("/usr/share/dict/words", 3, 6);
        final String alphabet = "abcdefghifjklmnopqrstuvwxyz";
        String[] words = new String[22];
        for (int i = 0; i < words.length; i++)
            words[i] = alphabet.substring(i, i + 6);

        // warmup the code
        for (int i = 0; i < 12000; i += words.length)
            for (String word : words)
                dict.allWordsFor(word);
        // time to do 20 searches
        Map<String, Set<String>> searches = new LinkedHashMap<>();
        long start = System.nanoTime();
        for (String word : words)
            searches.put(word, dict.allWordsFor(word));
        long time = System.nanoTime() - start;

        System.out.printf("Took an average of %.1f micro-seconds, searching %,d words%n",
                time / words.length / 1e3, dict.count);
        for (Map.Entry<String, Set<String>> entry : searches.entrySet()) {
            System.out.println(entry);
        }
    }

}

class Dictionary {
    private final int min;
    Map<String, List<String>> wordForLetters = new HashMap<>();
    int count = 0;

    public Dictionary(String filename, int min, int max) throws IOException {
        this.min = min;
        try (BufferedReader br = new BufferedReader(new FileReader(filename))) {
            for (String line; (line = br.readLine()) != null; ) {
                if (line.length() >= min && line.length() <= max) {
                    char[] chars = line.toLowerCase().toCharArray();
                    Arrays.sort(chars);
                    String sorted = new String(chars);
                    List<String> words = wordForLetters.get(sorted);
                    if (words == null)
                        wordForLetters.put(sorted, words = new ArrayList<>());
                    words.add(line);
                    count++;
                }
            }
        }
    }

    public Set<String> allWordsFor(String s) {
        Set<String> allWords = new TreeSet<>();
        String lower = s.toLowerCase();
        for (int i = (1 << min) - 1; i < (1 << s.length()); i++) {
            int bitCount = Integer.bitCount(i);
            if (bitCount < min) continue;
            StringBuilder sb = new StringBuilder(bitCount);
            for (int j = 0; j < s.length(); j++)
                if (((i >> j) & 1) != 0)
                    sb.append(lower.charAt(j));
            final List<String> words = wordForLetters.get(sb.toString());
            if (words != null)
                allWords.addAll(words);
        }
        return allWords;
    }
}

Took an average of 9.1 micro-seconds, searching 22,299 words
abcdef=[Abe, Dec, Feb, Fed, abed, ace, aced, bad, bade, bead, bed, cab, cad, dab, deaf, deb, decaf, face, faced, fad, fade, fed]
bcdefg=[Dec, Feb, Fed, bed, beg, deb, fed]
cdefgh=[Che, Dec, Fed, chef, fed]
defghi=[Fed, Gide, die, dig, fed, fie, fig, hid, hide, hie, hied]
efghif=[fie, fig, hie]
fghifj=[fig, jig]
ghifjk=[JFK, jig]
hifjkl=[JFK, ilk]
ifjklm=[JFK, Jim, Kim, ilk, mil, milk]
fjklmn=[JFK]
jklmno=[Jon, Lon, Mon, Monk, monk]
klmnop=[Lon, Mon, Monk, Polk, lop, monk, mop, pol]
lmnopq=[Lon, Mon, Qom, lop, mop, pol]
mnopqr=[Mon, Qom, Ron, mop, morn, nor, norm, porn, pro, prom, romp]
nopqrs=[Ron, Son, nor, porn, pro, pros, son, sop]
opqrst=[Post, opt, opts, port, ports, post, pot, pots, pro, pros, rot, rots, sop, sort, sot, sport, spot, stop, strop, top, tops, tor, tors]
pqrstu=[Prut, Stu, pus, put, puts, rust, rut, ruts, spur, spurt, sup, ups]
qrstuv=[Stu, rust, rut, ruts]
rstuvw=[Stu, rust, rut, ruts]
stuvwx=[Stu, tux]
tuvwxy=[tux]
uvwxyz=[]

#7 楼

    for(String word : sortedDictionary){
        char[] anagramCharacters = anagram.toCharArray();
        int i2, i3;
        for(i2 = 0; i2 < word.length(); i2++){
            char wordChar = word.charAt(i2);
            for(i3 = 0; i3 < anagramCharacters.length; i3++){
                if(wordChar == anagramCharacters[i3]){
                    anagramCharacters[i3] = 0;
                    break;
                }
            }
            // break out if wordChar did not match any anagramCharacters
            if(i3 == anagramCharacters.length)
                break;
        }
        // add the word if all letters were found in the anagram letters
        if(i2 == word.length())
            anagram_words.add(word);
    }

    for(String word : sortedDictionary){
        char[] anagramCharacters = anagram.toCharArray();
        boolean anagramOK = true;
        for(char wordChar : word.toCharArray()){
            boolean found = false;
            for(int i = 0; !found && i < anagramCharacters.length; i++){
                if(wordChar == anagramCharacters[i]){
                    anagramCharacters[i] = 0;
                    found = true;
                }
            }
            // if not found, the word is not compatible with the anagram letters
            if(!found){
                anagramOK = false;
                break;
            }
        }
        // add the word if all letters were found in the anagram letters
        if(anagramOK)
            anagram_words.add(word);
    }