Ambiguity in expected answer

  • 0

    The example given in the question does not make sense to me :

    Given s = "aab",

    Why do we have to add "b" twice in the answer ?

    I attempted a brute force solution but, it is failing on a similar case as above :

    Input:	"cdd"
    Output:	[["c","d","d"],["dd"]]
    Expected:	[["c","d","d"],["c","dd"]]

    Here is my implementation, it simply checks if all possible substrings are palindrome or not.

    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<List<String>>();
        for (int i = 0; i < s.length(); i++) {
            List<String> palindromes = new ArrayList<String>();
            for (int j = 0; j < s.length() - i; j++) {
                String currentSubstring = s.substring(j, j + i + 1);
                if (isPalindrome(currentSubstring)) palindromes.add(currentSubstring);
            if(palindromes.size() > 0) result.add(palindromes);
        return result;
    private boolean isPalindrome(String s) {
        if (s == null || s.length() == 0) return true;
        for (int i = 0, j = s.length() - 1; i < j; i++, j--)
            if (s.charAt(i) != s.charAt(j)) return false;
        return true;

    It may not be able to pass time limit tests, but I feel it should pass the correctness tests. What do you think ?

  • 0

    you need to "partition s" first, and then check the substring of each partition parts.

     Input:  "cdd"
     Output: [["c","d","d"],["dd"]]   > "dd" is just a substring of "cdd", not a full parttion
     Expected:   [["c","d","d"],["c","dd"]] > 2 ways to partition "cdd"

  • 0

    Thanks. But, what are the basis of partitioning the string ? First you do partition of length one, then two ? "c" in ["c", "dd"] don't quite fit in this way as its of length 1.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.