681. Next Closest Time

681. Next Closest Time

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 is next day's time since it is smaller than the input time numerically.

----------------------------------
把所有的时间组合都找出来，去掉不合法的，然后排序。
另一个方法是模拟始终，一步步往前走

class Solution {
    public String nextClosestTime(String time) {
        Set<Character> set = new HashSet<>();
        for (int i = 0; i < time.length(); i++) {
            char c = time.charAt(i);
            if (c != ':') set.add(c);
        }
        
        Set<String> rt = new HashSet<>();
        rt.add("");
        for (int i = 0; i < 4; i++) {
            Set<String> tmp = new HashSet<>();
            for (String s : rt) {
                for (Character c : set) {
                    String ca = s + c;
                    if (i == 3) {
                        if (isValid(ca))
                            tmp.add(s + c);
                    }else {
                        tmp.add(s + c);
                    }
                }    
            }
            rt = tmp;
            
        }
        
        List<String> fi = new ArrayList<String>(rt);
        Collections.sort(fi);
        String con = time.substring(0, 2) + time.substring(3);
        for (int i = 0; i < fi.size(); i++) {
            if (fi.get(i).equals(con) && i < fi.size() - 1) {
                return fi.get(i + 1).substring(0, 2) + ":" + fi.get(i + 1).substring(2);
            }
        }
        
        return fi.get(0).substring(0, 2) + ":" + fi.get(0).substring(2);
    }
    
    private boolean isValid(String s) {
        String firstHalf = s.substring(0,2);
        String secondHalf = s.substring(2);
        if (firstHalf.compareTo("23") > 0 || secondHalf.compareTo("59") > 0) return false;
        
        return true;
    }
}