检查是否可以从给定的一组字符串组成给定的字符串

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

Answer 2

简单检查输入的字符串是否包含列表中的子字符串。如果剩下任何字母，则它不是由这些子字符串组成的，并返回 false。尝试如下代码。

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;

}

Answer 3

检查字符串是否是从子字符串列表构建的算法 这是一个解决方案。我很想知道一些IO平台是否有这个算法问题。看起来真的很经典。