Java 3ms Backtracking solution


  • 0
    E

    combine hour and minute into an array and start doing backtracking on it, similar to subsets, the first 4 numbers represents candidates for hour and the rest represents candidates for minutes, discard all the hours and minutes that overflow

    public class Solution {
        public List<String> readBinaryWatch(int num) {
            List<String> result = new LinkedList<>();
            if (num < 1) {
                result.add("0:00");
                return result;
            }    
            int[] time = {8, 4, 2, 1, 32, 16, 8, 4, 2, 1};
            helper(time, 0, 0, 0, 0, num, result);
            return result;
        }
        private void helper(int[] time, int hour, int minute, int index, int count, int num, List<String> result) {
            if (count == num) {
                StringBuilder sb = new StringBuilder();
                sb.append(hour);
                sb.append(":");
                if (minute < 10) {
                    sb.append(0);
                }
                sb.append(minute);
                result.add(0, sb.toString());
            }
            for (int i = index; i < time.length; i++) {
                if (i < 4) {
                    hour += time[i];
                } else {
                    minute += time[i];
                }
                if (hour >= 12) {
                    hour -= time[i];
                    continue;
                }
                if (minute > 59) {
                    minute -= time[i];
                    continue;
                }
                helper(time, hour, minute, i + 1, count + 1, num, result);
                if (i < 4) {
                    hour -= time[i];
                } else {
                    minute -= time[i];
                }
            }
            
        }
    }
    

Log in to reply
 

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