split strings with backtracking

Question

I'm trying to write a code that split a spaceless string into meaningful words but when I give sentence like "arealways" it returns ['a', 'real', 'ways'] and what I want is ['are', 'always'] and my dictionary contains all this words. How can I can write a code that keep backtracking till find the best matching?

the code that returns 'a', 'real', 'ways':

splitter.java:

public class splitter {

    HashMap<String, String> map = new HashMap<>();
    Trie dict;

    public splitter(Trie t) {
        dict = t;
    }

    public String split(String test) {
        if (dict.contains(test)) {
            return (test);
        } else if (map.containsKey(test)) {
            return (map.get(test));
        } else {
            for (int i = 0; i < test.length(); i++) {
                String pre = test.substring(0, i);
                if (dict.contains(pre)) {
                    String end = test.substring(i);
                    String fixedEnd = split(end);
                        if(fixedEnd != null){
                            map.put(test, pre + " " + fixedEnd);
                            return pre + " " + fixedEnd;
                        }else {
                        }
                    
                }
            }

        }
        map.put(test,null);
        return null;
    }
} 

Trie.java:

public class Trie {
    public static class TrieNode {
        private HashMap<Character, TrieNode> charMap = new HashMap<>();
        public char c;
        public boolean endOWord;
        public void insert(String s){
        }
        public boolean contains(String s){
            return true;
        }
    }
    public TrieNode root;
    
    public Trie() {
        root = new TrieNode();
    }
    
    public void insert(String s){
        TrieNode p = root;
        for(char c : s.toCharArray()) {
            if(! p.charMap.containsKey(c)) {
                TrieNode node = new TrieNode();
                node.c = c;
                p.charMap.put(c, node);
            }
            p = p.charMap.get(c);
        }
        p.endOWord = true;
    }
    public boolean contains(String s){
        TrieNode p = root;
        for(char c : s.toCharArray()) {
            if(!p.charMap.containsKey(c)) {
                return false;
            }
            p = p.charMap.get(c);
        }
        return p.endOWord;
    }
    public void insertDictionary(String filename) throws FileNotFoundException{
        File file = new File(filename);
        Scanner sc = new Scanner(file);
        while(sc.hasNextLine())
            insert(sc.nextLine());
    }
    

    public void insertDictionary(File file) throws FileNotFoundException{
        Scanner sc = new Scanner(file);
        while(sc.hasNextLine())
            insert(sc.nextLine());
    }
} 

WordSplitter class:

public class WordSplitter {

    public static void main(String[] args) throws FileNotFoundException {
            
           String test = "arealways";
           String myFile = "/Users/abc/Desktop/dictionary.txt";
           Trie dict = new Trie();
           dict.insertDictionary(myFile);
          splitter sp = new splitter(dict);
          test = sp.split(test);
          
          if(test != null)
          System.out.println(test);
          else
          System.out.println("No Splitting Found.");            
           
    }

        } 

Answer 1

Using the OP's split method and the implementation of Trie found in The Trie Data Structure in Java Baeldung's article, I was able to get the following results:

realways=real ways
arealways=a real ways

However, if I remove the word "real" or "a" from the dictionary, I get the following results:

realways=null
arealways=are always

Here's the entire code I used to get these results:

public class Splitter {

    private static Map<String, String> map = new HashMap<>();
    private Trie dict;
    
    public Splitter(Trie t) {
        dict = t;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        List<String> words = List.of("a", "always", "are", "area", "r", "way", "ways"); // The order of these words does not seem to impact the final result
        String test = "arealways";

        Trie t = new Trie();
        for (String word : words) {
            t.insert(word);
        }
        System.out.println(t);
        Splitter splitter = new Splitter(t);
        splitter.split(test);
        map.entrySet().forEach(System.out::println);
    }

    public String split(String test) {
        if (dict.find(test)) {
            return (test);
        } else if (map.containsKey(test)) {
            return (map.get(test));
        } else {
            for (int i = 0; i < test.length(); i++) {
                String pre = test.substring(0, i);
                if (dict.find(pre)) {
                    String end = test.substring(i);
                    String fixedEnd = split(end);
                    if (fixedEnd != null) {
                        map.put(test, pre + " " + fixedEnd);
                        return pre + " " + fixedEnd;
                    } else {
                    }

                }
            }

        }
        map.put(test, null);
        return null;
    }

    public static class Trie {
        private TrieNode root = new TrieNode();

        public boolean find(String word) {
            TrieNode current = root;
            for (int i = 0; i < word.length(); i++) {
                char ch = word.charAt(i);
                TrieNode node = current.getChildren().get(ch);
                if (node == null) {
                    return false;
                }
                current = node;
            }
            return current.isEndOfWord();
        }

        public void insert(String word) {
            TrieNode current = root;
            for (char l : word.toCharArray()) {
                current = current.getChildren().computeIfAbsent(l, c -> new TrieNode());
            }
            current.setEndOfWord(true);
        }
        
        @Override
        public String toString() {
            return toString(root);
        }

        /**
         * @param root2
         * @return
         */
        private String toString(TrieNode node) {
            return node.toString();
        }

        public static class TrieNode {
            private Map<Character, TrieNode> children = new HashMap<>() ;
            private String contents;
            private boolean endOfWord;

            public Map<Character, TrieNode> getChildren() {
                return children;
            }

            public void setEndOfWord(boolean endOfWord) {
                this.endOfWord = endOfWord;
            }

            public boolean isEndOfWord() {
                return endOfWord;
            }
            
            @Override
            public String toString() {
                StringBuilder sbuff = new StringBuilder();
                if (isLeaf()) {
                    return sbuff.toString();
                }
                children.entrySet().forEach(entry -> {
                    sbuff.append(entry.getKey() + "\n");
                });
                sbuff.append(" ");
                return children.toString();
            }
            
            private boolean isLeaf() {
                return children.isEmpty();
            }
        }
        
        public void delete(String word) {
            delete(root, word, 0);
        }

        private boolean delete(TrieNode current, String word, int index) {
            if (index == word.length()) {
                if (!current.isEndOfWord()) {
                    return false;
                }
                current.setEndOfWord(false);
                return current.getChildren().isEmpty();
            }
            char ch = word.charAt(index);
            TrieNode node = current.getChildren().get(ch);
            if (node == null) {
                return false;
            }
            
            boolean shouldDeleteCurrentNode = delete(node, word, index + 1) && !node.isEndOfWord();

            if (shouldDeleteCurrentNode) {
                current.getChildren().remove(ch);
                return current.getChildren().isEmpty();
            }
            return false;
        }
    }
}

I improved the original code by adding a toString() method to the Trie and TrieNode. Now, when I print out the Trie object "t", I get the following result:

{a={r={e={a=}}, l={w={a={y={s=}}}}}, w={a={y={s=}}}}

My conclusion is that the OP's TrieNode implementation is incorrect. The way the Trie is built, given the inputted string value, the behavior described by the OP seems to be correct.