DFS brute force but easy to understand


  • 0
    J

    DFS method came up through all valid combinations by sorted integer array, since the int array is sorted, to some extent, the time string is sorted accordingly. Then either it's the next one or the first one in list.

    class Solution {
        public String nextClosestTime(String time) {
            if (time.length() == 0) return "";
            char [] chars = time.toCharArray();
            int len = time.length();
            int[] arr = new int[chars.length-1];
            int index = 0;
            for (int i=0; i<chars.length; i++) {
                if (chars[i] != ':' ) {
                    arr[index++] = chars[i]-'0';
                }
            } // put time string into an int array
            Arrays.sort(arr);
            List<String> res = new ArrayList<>();
            dfs(arr, 0, "", res);
            // System.out.println(res);
            int i=0;
            while (i<res.size()) {
                if (time.equals(res.get(i))) {
                    break;
                }
                i++;
            }
            return (i == res.size()-1) ? res.get(0) : res.get(i+1);
        }
        public void dfs(int[] arr, int start, String temp, List<String> res) {
            if (temp.length() == 5) {
                if (!res.contains(temp)) {
                    res.add(new String(temp));    
                }
                return;
            }
            for (int i=start; i<arr.length; i++) {
                if (temp.length() == 0) {
                    if (arr[i] <= 2 && arr[i] >= 0) {
                        // System.out.println(temp);
                        dfs(arr, 0, temp+""+arr[i], res);        
                    } else {
                        continue;
                    }
                } else if (temp.length() == 1) {
                    if (temp.charAt(temp.length()-1) == '1' || temp.charAt(temp.length()-1) == '0') {
                        if (arr[i] <= 9 && arr[i] >= 0) {
                        dfs(arr, 0, temp+""+arr[i], res);
                        } else {
                        continue;
                        }    
                    } else {
                        if (arr[i] <= 3 && arr[i] >= 0) {
                            dfs(arr, 0, temp+""+arr[i], res);
                        } else {
                            continue;    
                        }
                    }
                    
                } else if (temp.length() == 2) {
                    dfs(arr, 0, temp+":", res);
                } else if (temp.length() == 3) {
                    if (arr[i] <= 5 && arr[i] >= 0) {
                        dfs(arr, 0, temp+"" + arr[i], res);
                    } else {
                        continue;
                    }
                } else if (temp.length() == 4) {
                    if (arr[i] <= 9 && arr[i] >= 0) {
                        dfs(arr,0,temp+""+arr[i], res);    
                    } else {
                        continue;
                    }   
                }
            }
        }
    }
    

Log in to reply
 

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