Question

How to check whether a string can be segmented into a sequence of words from a dictionary in Java

Answer 1

import java.util.Set;
import java.util.Arrays;
import java.util.HashSet;

public class WordBreak {

    public static boolean wordBreak(String s, Set<String> dict) {
        int slen = s.length();
        boolean[] result = new boolean[slen + 1];
        result[0] = true; // empty string is always segmentable

        for (int i = 1; i <= slen; i++) {
            for (int j = 0; j < i; j++) {
                if (result[j] && dict.contains(s.substring(j, i))) {
                    result[i] = true;
                    break;
                }
            }
        }

        return result[slen];
    }

    public static void main(String[] args) {
        Set<String> dict = new HashSet<>(Arrays.asList(
            "future", "depends", "the", "on",
            "your", "dreams", "start", "today"
        ));

        String s = "futuredependsonyourdreams";

        if (wordBreak(s, dict)) {
            System.out.println("The string can be segmented");
        } else {
            System.out.println("The string cannot be segmented");
        }
    }
}


/*
run:

The string can be segmented

*/

 

70+ SQL courses for beginners and professionals

Answer 2

import java.util.List;
import java.util.Arrays;

public class WordBreakRecursive {

    public static boolean isInDict(String word, List<String> dict) {
        for (String d : dict) {
            if (d.equals(word)) {
                return true;
            }
        }
        return false;
    }

    public static void wordBreak(String str, int strSize, String result, List<String> dict) {
        for (int i = 1; i <= strSize; i++) {
            String subStr = str.substring(0, i);

            if (isInDict(subStr, dict)) {
                if (i == strSize) {
                    result += subStr;
                    System.out.println(result);
                    return;
                }
                wordBreak(str.substring(i), strSize - i, result + subStr + " ", dict);
            }
        }
    }

    public static void main(String[] args) {
        String str = "butterflyplaybasketballwithbags";
        
        List<String> dict = Arrays.asList(
            "butterfly", "basketball", "bagpiper", "and", "play",
            "with", "butter", "fly", "basket", "ball", "bags"
        );

        wordBreak(str, str.length(), "", dict);
    }
}



/*
run:

butter fly play basket ball with bags
butter fly play basketball with bags
butterfly play basket ball with bags
butterfly play basketball with bags

*/

 

70+ SQL courses for beginners and professionals