CODEWITHSUNDEEP
javastringdynamic-programming
javaboy
javaboy

Reputation: 29

Check if a given string can be made from a given set of strings

How to check if a given string can be made from a given set of strings? In the set of given strings, any string can be used any number of times only these strings can't be splitted."

For e.g.,
given set of strings are:
<aaa, hh, aa, rr>

Strings to check:
rraaahh :: returns True
raahh :: returns False
aarrr :: returns True

Below I have written a function that selects any two strings from the set of strings and check if the given string can be made from the selected strings.

But how do I approach for taking more than two strings at a time where any string can be used multiple times.

static boolean isPossible(Vector<String> v, String str) 
{ 

    // Sort the given string 
    str = sortString(str); 

    // Select two strings at a time from given vector 
    for (int i = 0; i < v.size() - 1; i++) 
    { 
        for (int j = i + 1; j < v.size(); j++) 
        { 

            // Get the concatenated string 
            String temp = v.get(i) + v.get(j); 

            // Sort the resultant string 
            temp = sortString(temp); 

            // If the resultant string is equal 
            // to the given string str 
            if (temp.compareTo(str) == 0) 
            { 
                return true; 
            } 
        } 
    } 

    // No valid pair found 
    return false; 
}

Upvotes: 2

Views: 2701

Answers (2)

Helkaruthion
Helkaruthion

Reputation: 21

Simple replacement does not work, as "aaaa" always matches at first on "aaa", just leaving "a" as a rest. But you can solve it recursivly.

    public static void main(String[] args) {

    String input = "aaaarrrraahhaaa";

    ArrayList<String> list = new ArrayList<String>() {
        {
            add("aaa");
            add("hh");
            add("aa");
            add("rr");
        }
    };

    System.out.println(isPossible(list, input));

}

static boolean isPossible(List<String> fragments, String input) {
    return isOkay(fragments, input, "");
}

private static boolean isOkay(List<String> list, String input, String candidate) {
    for (int i = 0; i < list.size(); i++) {
        String testee = candidate + list.get(i);
        if (testee.equals(input)) {
            return true;
        }
        if (input.startsWith(testee)) {
            boolean tempResult = isOkay(list, input, testee);
            if (tempResult) {
                return true;
            }
        }
        testee = candidate;
    }
    return false;
}

Upvotes: 1

Wing Kui Tsoi
Wing Kui Tsoi

Reputation: 544

Simple check if the string input contains the substrings in list. If any letter is left, it is not made up by those substrings and return false. Try this code as follows.

public static void main(String[] args) {

    String input = "aarr";

    ArrayList<String> list = new ArrayList<String>() {{
        add("aaa");
        add("hh");
        add("aa");
        add("rr");
    }};

    System.out.println(isPossible(list, input));

}

static boolean isPossible(ArrayList<String> list, String input) { 

    int count = 4;

    for (String item : list) {
        if (input.contains(item)) {
            input = input.replace(item, "");
            System.out.println("Debug: " + input);
        }
    }

    if ((int) input.length() == 0) {
        System.out.println("Pass: " + input.length());
        return true;
    } else {
        System.out.println("Fail: " + input.length());
    }

    return false;

}

Upvotes: 0

Related Questions