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

Note

Method 1: O(n^2))

read all digits & dfs all possible compinations.

Find next larger min, replace current one.

Find next larget hour, replace current one, use smallest combination to replace min.

use smallest combination to replace both hour and min.

class Solution {
public:
    string nextClosestTime(string time) {
        set<int> tracker;
        set<int> digits;
        int hour = 0;
        int min = 0;
        bool found = false;

        for(int loop = 0; loop < time.size(); ++loop) {
            if(time[loop] == ':')
                continue;

            if(loop < 2) {
                hour = hour * 10 + time[loop] - '0';
            }
            else {
                min = min * 10 +time[loop] - '0';
            }

            digits.insert(time[loop] - '0');
        }

        for(auto iter = digits.begin(); iter != digits.end(); ++iter) {
            for(auto iter2 = digits.begin(); iter2 != digits.end(); ++iter2) {
                tracker.insert(*iter * 10 + *iter2);
            }
        }
        copy(tracker.begin(), tracker.end(), ostream_iterator<int>(cout, ","));
        cout << endl;

        auto candidate = tracker.upper_bound(min);
        if(candidate != tracker.end() && *candidate < 60) {
            time[4] = *candidate % 10 + '0';
            time[3] = *candidate / 10 + '0';
            found = true;
        }

        if(found == false) {
            candidate = tracker.upper_bound(hour);
            if(candidate != tracker.end() && *candidate < 24) {
                time[1] = *candidate % 10 + '0';
                time[0] = *candidate / 10 + '0';
                time[4] = *tracker.begin() % 10 + '0';
                time[3] = *tracker.begin() / 10 + '0';               
                found = true;
            } 
        }

        if(found == false) {
            time[1] = *tracker.begin() % 10 + '0';
            time[0] = *tracker.begin() / 10 + '0';
            time[4] = *tracker.begin() % 10 + '0';
            time[3] = *tracker.begin() / 10 + '0';             
        }

        return time;
    }
};

Method 2:

Digit by digit;

Method 3:

max value is 1440 (24*60), iterate candidate, validate possibilities.

class Solution {
    int mins[4] = { 600, 60, 10, 1 };
public:
    string nextClosestTime(string time) {
        size_t colon = time.find(':');
        int cur = stoi(time.substr(0, colon)) * 60 + stoi(time.substr(colon + 1));
        string next = "0000";
        for (int i = 1, d = 0; i <= 1440 && d < 4; i++) {
            int m = (cur + i) % 1440;
            for (d = 0; d < 4; d++) {
                next[d] = '0' + m / mins[d]; m %= mins[d];
                if (time.find(next[d]) == string::npos) break;
            }
        }
        return next.substr(0, 2) + ':' + next.substr(2, 2);
    }
};