Ambiguity in expected answer


  • 0
    R

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

    Given s = "aab",
    
    Return
    
      [
        ["aa","b"],
        ["a","a","b"]
      ]
    

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

    EDIT:
    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
    E

    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
    R

    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.