"short" java solution, beats 98%


  • 18
    M

    Since most top solutions are very long and it's uncomfortable to read, so I share my shorter solution, and it beats 98% java solution.

    My idea is simple and clear. it's just like a DFS or a Backtracking solution. word is poor, just look the code.

    '''
    public class Solution {

    int MAXCOUNT = 6;   // the max balls you need will not exceed 6 since "The number of balls in your hand won't exceed 5"
    
    public int findMinStep(String board, String hand) {
        int[] handCount = new int[26];
        for (int i = 0; i < hand.length(); ++i) ++handCount[hand.charAt(i) - 'A'];
        int rs = helper(board + "#", handCount);  // append a "#" to avoid special process while j==board.length, make the code shorter.
        return rs == MAXCOUNT ? -1 : rs;
    }
    private int helper(String s, int[] h) {
        s = removeConsecutive(s);     
        if (s.equals("#")) return 0;
        int  rs = MAXCOUNT, need = 0;
        for (int i = 0, j = 0 ; j < s.length(); ++j) {
            if (s.charAt(j) == s.charAt(i)) continue;
            need = 3 - (j - i);     //balls need to remove current consecutive balls.
            if (h[s.charAt(i) - 'A'] >= need) {
                h[s.charAt(i) - 'A'] -= need;
                rs = Math.min(rs, need + helper(s.substring(0, i) + s.substring(j), h));
                h[s.charAt(i) - 'A'] += need;
            }
            i = j;
        }
        return rs;
    }
    //remove consecutive balls longer than 3
    private String removeConsecutive(String board) {
        for (int i = 0, j = 0; j < board.length(); ++j) {
            if (board.charAt(j) == board.charAt(i)) continue;
            if (j - i >= 3) return removeConsecutive(board.substring(0, i) + board.substring(j));
            else i = j;
        }
        return board;
    }
    

    }
    '''


  • 1
    J

    This solution has accepted.

    But it output -1 in the case :"RRWWRRBBRR", "WB".
    The right output is 2.


  • 0
    J

    When I comment s = removeConsecutive(s); in function helper,
    then the solution will output 2 in the case :"RRWWRRBBRR", "WB".

    private int helper(String s, int[] h) {
    // s = removeConsecutive(s);
    if (s.equals("#")) return 0;
    ...

    Illustrate:
    After comment it,
    The 'RRRRBBRR' will not be removed.

    The process is : 'RRWWRRBBRR' -> 'RRWW[W]RRBBRR' -> 'RRRRBBRR' -> 'RRRRBB[B]RR' -> 'RRRRRR' -> ''

    Only need two inserts.


  • 0
    M

    yes, as @herbix mentioned, this test have not be included in test cases and the contributor have not think of this situation.

    sorry about that.

    I guess the intention of the contributor is to check wether their candidates have the ability to use DFS elegantly, but he does not realize that actually is a more difficult problem. And me too, sorry


  • 0
    This post is deleted!

  • 2
    D

    @justforcode no, it should output -1, the 4 Rs should be removed immediately, as there are more than 3 balls in the same color touching. That is how zuma works.


  • 0

    Nice solution, but I'm just wondering why did you initialize the handCount to be of size 32?
    To me, 26 is good enough and it also passes the OJ.


  • 0
    S

    @fishercoder yes, you are right, 26 is ok!


  • 0
    M

    @fishercoder yes,you are right. 26 is ok and it's better for comprehension. I use 32 maybe I think there 32 alphabet in upper case.....


Log in to reply
 

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