java - 检查给定的字符串是否可以由给定的一组字符串组成

Question

如何检查给定的字符串是否可以由给定的字符串集组成？在给定的字符串集合中，任何字符串都可以使用任意次数，只是这些字符串不能被拆分。"

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

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

下面我写了一个函数，它从字符串集合中选择任意两个字符串，并检查给定的字符串是否可以由所选字符串组成。

但是，如果任何字符串都可以多次使用，我该如何处理一次获取两个以上的字符串。

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; 
}

Answer 1

简单的替换是行不通的，因为“aaaa”总是首先匹配“aaa”，只留下“a”作为休息。但是你可以递归地解决它。

    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;
}