570. Find the Missing Number II

class Solution { public: /** * @param n: An integer * @param str: a string with number from 1-n in random order and miss one number * @return: An integer */ int findMissing2(int n, string &str) { // write your code here //DFS 分隔符放在一个char还是两个 if(n <= 1){ return -1; } vector<int> visited(n, 0); return dfs(n, str, 0, visited); } int dfs(int n, string &str, int start, vector<int> &visited){ //出口 if(start >= str.size()){ vector<int> missed; for(int i = 1; i <= n; i++){ if(!visited[i - 1]){ missed.push_back(i); } } if(missed.size() == 1){ return missed[0]; } else{ return -1; } } // body if(str[start] == '0'){ return -1; } for(int i = 1; i <= 2; i++){ if(start + i <= str.size()){ int tmpNum = stoi(str.substr(start, i)); if(tmpNum > n || tmpNum < 1 || visited[tmpNum - 1]){ continue; } visited[tmpNum - 1] = 1; int tmp = dfs(n, str, start + i, visited); if(tmp != -1){ return tmp; } visited[tmpNum - 1] = 0; } } return -1; } };