Giving a string with number from 1-n in random order, but miss 1 number.Find that number.

Example

Given n = 20, str = 19201234567891011121314151618 . return 17

public class Solution {
    /**
     * @param n: An integer
     * @param str: a string with number from 1-n in random order and miss one number
     * @return: An integer
     */

    // 
    public int ans = 0;
    public boolean flag;
    public int findMissing2(int n, String str) {
        // write your code here
        boolean[] nums = new boolean[n + 1];

        dfs(str,0,n,nums);
        return ans;
    }
    //once the flag is true, it indicates that we have found an answer, then we don't need to find any more;
    public void dfs(String str, int startIndex, int n, boolean[] nums) {
        if (flag) {
            return;
        }
        //the key point of find the final answer should be when we encountered the last char in str
        if (startIndex >= str.length()) {
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == false) {
                    ans = i;
                    flag = true;
                    return;
                }
            }
        }
        int num = str.charAt(startIndex) - '0';
        if (num == 0) {
            return;
        }
        int ptr = startIndex;
        while (num <= n) {
            // if the number have not been found before, then we try it
            //after we tried it, we have to recover it, so that we could try if it could be a total number with the number next 
            //to it.
            if (nums[num] == false) {
                nums[num] = true;
                dfs(str, ptr + 1, n, nums);
                nums[num] = false;
            }

            ptr++;
            if (ptr >= str.length()) {
                break;
            }
            num = num * 10 + str.charAt(ptr)-'0';
        }

    }
}

典型的dfs，split string类型

可以取当前这个数字，也可不取，都试一试

每个char走一遍，没有count就将它对应的count设为true， 如果不是valid number， 跳过循环，同时有一个flag，一旦找到答案，以后的都不再找。 找到答案的条件是index能走到str的末尾。代码如下：

关键点在于，找到的条件是，遍历到最后一个str的位置。同时，一旦前面flag已经设置为true之后，后面都不需要再找了