Java solution with preliminary indexation, beats 95%


  • 1
    A

    Basically the solution is standard recursive forward traversing of the string creating chains of substrings that are palindromes. Although there is lots of repeating work for checking substrings to be palindromes. To remove this caveat we can prepare the two-level matrix boolean[][] palindromes of all palindromes in the string that will show answer the question "Is there palindrome in the substring (i, j)?" in linear time.
    Indexing is pretty straightforward as well as traversing

    public List<List<String>> partition(String s) {
        boolean[][] palindromes = findAllPalindromes(s);
        List<List<String>> result = new ArrayList<>();
        partition(s, 0, palindromes, new ArrayList<>(), result);
        return result;
    }
    
    public boolean[][] findAllPalindromes(String s) {
        if (s.length() == 1) {
            return new boolean[][]{{true, true}};
        }
        boolean[][] palindromes = new boolean[s.length()][s.length()];
        for (int idx = 0; idx < s.length(); idx++) {
            // Case 1: the character is at the center of palindrome
            for (int i = idx, p = idx; i >= 0 && p < s.length(); i--, p++) {
                if (s.charAt(i) != s.charAt(p))
                    break;
                palindromes[i][p] = true;
            }
    
            // Case 2: character is the same as its neighbour
            if (idx < s.length() - 1) {
                for (int i = idx, p = idx + 1; i >= 0 && p < s.length(); i--, p++) {
                    if (s.charAt(i) != s.charAt(p))
                        break;
                    palindromes[i][p] = true;
                }
            }
        }
    
        return palindromes;
    }
    
    public void partition(String s, int idx, boolean[][] p, List<String> current, List<List<String>> result) {
        if (idx == s.length()) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = idx; i < s.length(); i++) {
            if (p[idx][i]) {
                current.add(s.substring(idx, i + 1));
                partition(s, i + 1, p, current, result);
                current.remove(current.size() - 1);
            }
        }
    }

Log in to reply
 

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