Reading an ArrayList Faster

Here is complete rewrite of the algorithm using indexing on all positions and characters. First this algorithm finds the shortest list of the words with a specified character at the specified position found in the pattern. Then it calculates cross section with all other lists of the words (one list per non-star character in the pattern).

import java.util.*;

public class CWSolution {

    class FixLengthDB {
        // Index -> Letter -> All word with the Letter at Index
        HashMap<Integer, HashMap<Character, Set<String>>> indexLetterDb = new HashMap<>();

        public void storeWord(String word) {
            int l = word.length();
            for (int i = 0; i < l; i++) {
                HashMap<Character, Set<String>> letterDb = indexLetterDb.get(i);
                if (letterDb == null) {
                    letterDb = new HashMap<>();
                    indexLetterDb.put(i, letterDb);
                }

                Set<String> list = letterDb.get(word.charAt(i));
                if (list == null) {
                    list = new HashSet<>();
                    letterDb.put(word.charAt(i), list);
                }

                list.add(word);
            }
        }

        public Set<String> getList(int i, char c) {
            HashMap<Character, Set<String>> letterDb = indexLetterDb.get(i);
            if (letterDb == null) {
                return null;
            }
            return letterDb.get(c);
        }
    }

    //create the data structure that will store the dictionary
    private HashMap<Integer,FixLengthDB> db = new HashMap<>();
    private List<String> allWords;

    public CWSolution(List<String> allWords)
    {

        //construct the background structure

        this.allWords = allWords;
        //go through each word
        for(String item : allWords) {
            FixLengthDB fixLengthDB = db.get(item.length());

            if (fixLengthDB == null) {
                fixLengthDB = new FixLengthDB();
                db.put(item.length(), fixLengthDB);
            }

            fixLengthDB.storeWord(item);
        }
    }

    public List<String> solutions(String pattern, int maxRequired)
    {

        FixLengthDB fixLengthDB = db.get(pattern.length());
        if (fixLengthDB == null) {
            return new ArrayList<>();
        }

        Set<String> shortList = null;
        int shortListIndex = 0;
        int l = pattern.length();
        for (int i = 0; i < l; i++) {
            if (pattern.charAt(i) == '*') {
                continue;
            }
            Set<String> set = fixLengthDB.getList(i, pattern.charAt(i));
            if (set == null) {
                return new ArrayList<>();
            }

            if (shortList == null || shortList.size() > set.size()) {
                shortList = set;
                shortListIndex = i;
            }
        }

        if (shortList == null) {
            return allWords;
        }

        HashSet<String> result = new HashSet<>(shortList);
        for (int i = 0; i < l; i++) {
            if (i == shortListIndex || pattern.charAt(i) == '*') {
                continue;
            }
            Set<String> set = fixLengthDB.getList(i, pattern.charAt(i));
            result.retainAll(set);
        }

            // TODO truncate result list according to 'maxRequired' parameter
    return new ArrayList<>(result);
    }
}

Explanation: The algorithm works in two steps

• Build an index (in the constructor)
• Use index to find matched words (solutions(...))

Build index: The index maintain the sets of string for each word-length/character-index/character.

Here how we add words to the index

Add word: fun
          |||
          ||\--- (length: 3, position 3, character 'n') -> set{"fun"})
          |\---- (length: 3, position 2, character 'u') -> set{"fun"})
          \----- (length: 3, position 1, character 'f') -> set{"fun"})

Add word: run
          |||
          ||\--- (length: 3, position 3, character 'n') -> set{"fun, run"})
          |\---- (length: 3, position 2, character 'u') -> set{"fun, run"})
          \----- (length: 3, position 1, character 'r') -> set{"run"})

Add word: raw
          |||
          ||\--- (length: 3, position 3, character 'w') -> set{"raw"})
          |\---- (length: 3, position 2, character 'a') -> set{"raw"})
          \----- (length: 3, position 1, character 'r') -> set{"run, raw"})

Add word: rar
          |||
          ||\--- (length: 3, position 3, character 'r') -> set{"rar"})
          |\---- (length: 3, position 2, character 'a') -> set{"raw, rar"})
          \----- (length: 3, position 1, character 'r') -> set{"run, raw, rar"})

The database after adding four words (fun, run, raw, rar) is

(length: 3, position 1, character 'f') -> set{"fun"})
(length: 3, position 1, character 'r') -> set{"run, raw, rar"})
(length: 3, position 2, character 'u') -> set{"fun, run"})
(length: 3, position 2, character 'a') -> set{"raw, rar"})
(length: 3, position 3, character 'w') -> set{"raw"})
(length: 3, position 3, character 'r') -> set{"rar"})
(length: 3, position 3, character 'n') -> set{"fun, run"})

Use index: How lets match the pattern ru*

First lets find the matching smallest set in the index. We have only 2 non-star characters, so we checking only two sets

1: (length: 3, position 1, character 'r') -> set{"run, raw, rar"})
2: (length: 3, position 2, character 'u') -> set{"fun, run"})

The smallest set is #2 {"fun, run"}. Now we iterate through all other matching sets (in our case the set #1) and calculate intersections:

{"fun, run"} cross {"run, raw, rar"} => {"run"}

The result is {"run"}.