2
\$\begingroup\$

The question is explained well by examples in the comments below. Also I request verifying complexity: O( n * n!), where n is the number of words in the subsets. Review my code for optimizations, best practices etc.

/**
 * Question is better explained by examples:
 * 1. given
 *    i/p subsets  - ["un", "xy", "te", "i", "d"]
 *    and i/p string is : united should result in true.
 *    and i/p string of : union should result in false.
 *  
 * 2. i/p subsets - ["tonyl", "pqr", "pqrbri",] 
 *    and i/p string of : briton should be true.
 *    and i/p string of : japan should result in false.
 *
 * Complexity: O( n * n!) where n is numnber of subset words.
 *
 */
public final class StringFromSubSets {

    private StringFromSubSets() {}

    private static int getFactorial (int length) {
        int factorial = 1;
        for (int i = 1; i <= length; i++) {
            factorial = factorial * i;
        }
        return factorial;
    }


    private static void swapWithNext (List<String> subStrings, int i) {
        assert subStrings != null;
        assert i >= 0 && i < subStrings.size() - 1; 

        String str = subStrings.get(i);
        subStrings.set(i, subStrings.get(i + 1));
        subStrings.set(i + 1, str);
    }


    private static String join (List<String> list) {
        assert list != null;

        final StringBuffer sb = new StringBuffer();
        for (String str : list) {
            sb.append(str);
        }
        return sb.toString();
    }


    private static Set<String> getPermutations(List<String> subStrings) {
        assert subStrings != null;

        final Set<String> set = new HashSet<String>();
        int factorial = getFactorial(subStrings.size());
        int counter = 0;

        while (counter < factorial) {
            for (int i = 0; i < subStrings.size() - 1; i++) {
                swapWithNext (subStrings, i);   // O(1)
                String joinedString = join (subStrings); // O(n)
                set.add(joinedString);
                counter++;
            }
        }
        return set;
    }


    public static boolean stringGotFromSubSets(List<String> subStrings, String wordToFind) {
        if (subStrings == null) {
            throw new NullPointerException("The substring provided is null.");
        }

        final Set<String> joinedStrings = getPermutations(subStrings);
        for (String joinedString : joinedStrings) {
            if (joinedString.contains(wordToFind)) return true;
        }

        return false;
    }


    public static void main(String[] args) {
        List<String> listOfString = new ArrayList<String>();
        listOfString.add("sachin");
        listOfString.add("tendulkar");
        listOfString.add("rahul");
        listOfString.add("dravid");
        System.out.println("Expected true, Actual " + stringGotFromSubSets(listOfString, "int"));
        System.out.println("Expected true, Actual " + stringGotFromSubSets(listOfString, "idsa"));
        System.out.println("Expected true, Actual " + stringGotFromSubSets(listOfString, "sachindravid"));

        System.out.println("Expected false, Actual " + stringGotFromSubSets(listOfString, "sehwag"));
        System.out.println("Expected false, Actual " + stringGotFromSubSets(listOfString, "ganguly"));
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ I don't get it. What is your algorithm supposed to do? \$\endgroup\$ – Jens Schauder Dec 21 '13 at 11:55
  • \$\begingroup\$ the original code isn't correct and doesn't do what it is supposed to do as pointed out by @200_succes \$\endgroup\$ – Malachi Dec 22 '13 at 15:12
  • 1
    \$\begingroup\$ Revised code here: codereview.stackexchange.com/q/37930 \$\endgroup\$ – 200_success Dec 23 '13 at 2:25
6
\$\begingroup\$

There are a number of things that are problematic.

most fundamental is the algorithm you are choosing to run. It does indeed appear to be something like O(n!) complexity. This is unsustainable.... and needs to be resolved.What it means is that your solution will effectively be unusable for more than 13 members of the list. This is especially true because you store all combinations in a single set... which is 'insane'.

What you are doing is searching for a needle in a haystack, and first you build the haystack ;-).

Instead, you need to use a better algorithm (take a magnet to the haystack ...).

But, dealing with your first issues first:

  • there is almost never any reason (unless you use java.util.regex.Matcher) to use StringBuffer. use StringBuilder instead.
  • your asserts are OK, but you need to also assert that the size of the list is less than 13, because 12! is the largest factorial that fits in an int. Changing it to a long won't help because you can't have a set with more than Integer.MAX_VALUE members anyway.
  • the other issues I have with your code stem from the fact you are using the wrong algorithm.....

Now, if this was my problem, I would restructure it entirely.

I would have one method that loops through all the members of the input set, and checks to see whether there's an overlap at the 'end' of the String, then I would split that matching value and keep the unused prefix, and then recursively search the remaining values.... let's explain that with pseudo code:

function: searchSequence(target, values)
    foreach (value : values)
        if (lastPartOfValueStarts(value, target)
            String matchingsuffix = matchingPartOf(value);
            String notmatchingprefix = restOf(value);
            Set candidates = values
            candidates.remove(value)
            candidates.add(nonmatchingprefix)
            if (recursiveSearch(target, lengthOf(matchingsuffix)))
                 return true;

function: recursiveSearch(target, fromindex, candidates)
    String remainder = target.substring(fromindex)
    foreach (candidate : candidates)
        if (candidate.startsWith(remainder))
            return true;
        if (remainder.startsWith(candidate))
            Set others = candidates.duplicate()
            others.remove(candidate)
            if (recursiveSearch(target, fromindex + lengthOf(candidate), others))
                return true
    return false
| improve this answer | |
\$\endgroup\$
7
\$\begingroup\$

Your getPermutations() fails to generate all permutations. Consider…

public static void main(String[] args) {
    List<String> list = Arrays.asList(args);
    for (String s : getPermutations(list)) {
        System.out.println(s);
    }
}

If you run java StringFromSubSets 0 1 2 3 | sort, the result is:

0123
0132
0312
1023
1203
1230
2130
2301
2310
3012
3021
3201

There should be 4! = 24 permutations, but you have produced only 12. For example, where is 0321? In other words,

public static void main(String[] args) {
    // Simpler initialization than the original
    List<String> listOfString = Arrays.asList(new String[] {
        "sachin", "tendulkar", "rahul", "dravid"
    });
    System.out.println("Expected true, Actual " +
        stringGotFromSubSets(listOfString, "drahultendulkars"));
}

… prints Expected true, Actual false.

| improve this answer | |
\$\endgroup\$

Not the answer you're looking for? Browse other questions tagged or ask your own question.