Return to Answer

add dynamic programming code to previous exhaustive search

Source Link

edited Feb 17, 2015 at 9:19

If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows (Top down style dynamic programming):

public class Connector {

    public static void main(String[] args) {

        List<String> resultstokens = new ArrayList<>ArrayList<String>(); // resultsinput
 are stored here     Connector connector = new Connector();
    
        @SuppressWarnings("unused")
        List<String> ret = connector.connect(tokens,);
 results   }

    Map<Integer, "");List<String>> //cache;
 the call  List<String> tokens;

void    public List<String> connect(List<String> tokens) {
        this.cache = new HashMap<Integer, List<String>>();
        this.tokens = tokens;
        List<String> resultsret = connect(tokens, String0);
 prefix       return ret;
    }


    List<String> connect(List<String> tokens, int start) {
        if (tokenscache.sizecontainsKey(start)) =={
 0           return cache.get(start);
        } else {
            List<String> results = new ArrayList<String>();
            connectHelper(tokens, start, results);
            cache.addput(prefixstart, results);
        return;    return results;
        }
    } 


    void connectHelper(List<String> tokens, int start, List<String> results) {
        int n = tokens.size();
        for(int i = start + 1; i < n; i++) {
            String part = concat(tokens, start, i);
            if (dictContains(part)) {
                List<String> restParts = connect(tokens.subList(, i);
 + 1, n             for(String oneRestPart : restParts), results,{
 prefix                   results.add(part + " " + partoneRestPart);
                }
            }
        }
    }

    static private String concat(List<String> tokens, int nlow, int hi) {
        StringBuilder sb = new StringBuilder();
        for(int i = 0;low; i < n;hi; i++) {
            sb.append(tokens.get(i));
        }
        return sb.toString();
    }
}

If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows:

List<String> results = new ArrayList<>(); // results are stored here
connect(tokens, results, ""); // the call

void connect(List<String> tokens, List<String> results, String prefix) {
    if (tokens.size() == 0) {
        results.add(prefix);
        return;
    }
    
    int n = tokens.size();
    for(int i = 1; i < n; i++) {
        String part = concat(tokens, i);
        if (dictContains(part)) {
            connect(tokens.subList(i + 1, n), results, prefix + " " + part);
        }
    }
}

private String concat(List<String> tokens, int n) {
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < n; i++) {
        sb.append(tokens.get(i));
    }
    return sb.toString();
}

If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows (Top down style dynamic programming):

public class Connector {

    public static void main(String[] args) {

        List<String> tokens = new ArrayList<String>(); // input
        Connector connector = new Connector();
    
        @SuppressWarnings("unused")
        List<String> ret = connector.connect(tokens);
    }

    Map<Integer, List<String>> cache;
    List<String> tokens;

    public List<String> connect(List<String> tokens) {
        this.cache = new HashMap<Integer, List<String>>();
        this.tokens = tokens;
        List<String> ret = connect(tokens, 0);
        return ret;
    }


    List<String> connect(List<String> tokens, int start) {
        if (cache.containsKey(start)) {
            return cache.get(start);
        } else {
            List<String> results = new ArrayList<String>();
            connectHelper(tokens, start, results);
            cache.put(start, results);
            return results;
        }
    } 


    void connectHelper(List<String> tokens, int start, List<String> results) {
        int n = tokens.size();
        for(int i = start + 1; i < n; i++) {
            String part = concat(tokens, start, i);
            if (dictContains(part)) {
                List<String> restParts = connect(tokens, i);
                for(String oneRestPart : restParts) {
                    results.add(part + " " + oneRestPart);
                }
            }
        }
    }

    static private String concat(List<String> tokens, int low, int hi) {
        StringBuilder sb = new StringBuilder();
        for(int i = low; i < hi; i++) {
            sb.append(tokens.get(i));
        }
        return sb.toString();
    }
}

Source Link

created Feb 15, 2015 at 14:04

InformedA

Actually this is not an AI problem, this is pure programming question solved by dynamic programming.

If you simply want to connect the tokens into a list of correctly spelled words then you proceed as follows:

List<String> results = new ArrayList<>(); // results are stored here
connect(tokens, results, ""); // the call

void connect(List<String> tokens, List<String> results, String prefix) {
    if (tokens.size() == 0) {
        results.add(prefix);
        return;
    }
    
    int n = tokens.size();
    for(int i = 1; i < n; i++) {
        String part = concat(tokens, i);
        if (dictContains(part)) {
            connect(tokens.subList(i + 1, n), results, prefix + " " + part);
        }
    }
}

private String concat(List<String> tokens, int n) {
    StringBuilder sb = new StringBuilder();
    for(int i = 0; i < n; i++) {
        sb.append(tokens.get(i));
    }
    return sb.toString();
}