Next Closest Time

https://leetcode.com/problems/next-closest-time/description/

Given a time represented in the format "HH:MM", form the next closest time by reusing the current digits. There is no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, "01:34", "12:09" are all valid. "1:34", "12:9" are all invalid.

Example 1:

Input: "19:34"

Output: "19:39"

Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, which occurs 5 minutes later. It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"

Output: "22:22"

Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. It may be assumed that the returned time

Thoughts

有两种比较直观的解法, 一种是不断+1分钟, 判断新时间是否存在. O(1440). 还有就是搜索, 把所有可能的组合写出来依次判断是否差的最小, O(256).

Code

class Solution {
    public String nextClosestTime(String time) {
        int start = Integer.parseInt(time.substring(0, 2)) * 60 + Integer.parseInt(time.substring(3));
        int[] nums = new int[4], res = new int[4];
        for (int i = 0, j = 0; i < time.length(); ++i) {
            if (time.charAt(i) == ':') {
                continue;
            }
            nums[j++] = time.charAt(i) - '0';
        }

        int m = Integer.MAX_VALUE;
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                int hour = nums[i] * 10 + nums[j];
                if (hour > 23) {
                    continue;
                }
                for (int p = 0; p < 4; ++p) {
                    for (int q = 0; q < 4; ++q) {
                        int min = nums[p] * 10 + nums[q];
                        if (min > 59) {
                            continue;
                        }
                        int now = hour * 60 + min;
                        int diff = now > start ? now - start : now + 24 * 60 - start; 
                        if (diff < m) {
                            m = diff;
                            res[0] = nums[i];
                            res[1] = nums[j];
                            res[2] = nums[p];
                            res[3] = nums[q];
                        }
                    }
                }
            }
        }

        return res[0] + "" + res[1] + ":" + res[2] + "" + res[3]; 
    }
}

Analysis

时间复杂度O(4^4).