Typical DFS with clear explanation


  • 1
    S
    public List<String> readBinaryWatch(int num) {
    		String[] times = new String[] {"1h","2h","4h","8h","1m","2m","4m","8m","16m","32m"};
    		List<String> total = new ArrayList<String>();
    		List<String> result = new ArrayList<String>();
    		dfs(0, num, times, result, total);
    
    		return total;
        }
    // total is the final result placeholder
    // when any result reach the size of num, covert it to the correct time format, add to final result
    private void dfs(int start, int num, String[] times, List<String> result, List<String> total) {
        	if (result.size() == num) {
        		List<String> temp = new ArrayList<String>(result);
        		String timeRepresent = getTime(temp);
        		if (timeRepresent != null) {
        			total.add(timeRepresent);
        		}
        		return;
        	}
        	for (int i = start; i < times.length; i++) {
        		String time = times[i];
        		result.add(time);
        		dfs(i + 1, num, times, result, total);
        		result.remove(result.size() - 1);
        	}
        }
    // helper function to get correct time representation
    private String getTime(List<String> list) {
        	int hours = 0;
        	int minutes = 0;
        	for (int i = 0; i < list.size(); i++) {
        		String time = list.get(i);
        		if (time.contains("h")) {
        			String[] h = time.split("h");
        			hours += Integer.parseInt(h[0]);
        		}
        		if (time.contains("m")) {
        			String[] m = time.split("m");
        			minutes += Integer.parseInt(m[0]);
        		}
        	}
        	String connection = minutes < 10 ? ":0" : ":";
        	if (minutes < 60 && hours < 12) {
        		return hours + connection + minutes;
        	}
        	return null;
        }
    

Log in to reply
 

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