Strobogrammatic Number

Strobogrammatic Number I, 用一个String s = "00 11 88 696"去替代hashmap的写法，在查找是用s.contains(str)方法，让代码看起来更加简洁。

public class Solution {
    public boolean isStrobogrammatic(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }

        int i = 0, j = num.length() - 1;
        String s = "00 11 88 696";
        while (i <= j) {
            char c1 = num.charAt(i), c2 = num.charAt(j);
            if (!s.contains(c1 + "" + c2)) {
                return false;
            }
            i++;
            j--;
        }

        return true;
    }
}

Strobogrammatic Number II, 建一个char array，维护left和right指针，向中间update char array里的值，在left > right时， 把string加到结果中去。注意corner case， 当length > 1是， 不能以0起始。

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        List<String> result = new ArrayList<String>();
        if (n < 0) {
            return result;
        }

        char[] num1 = {'1', '8', '0', '9', '6'};
        char[] num2 = {'1', '8', '0', '6', '9'};
        char[] num = new char[n];

        dfs(result, num, num1, num2, 0);
        return result;
    }

    private void dfs(List<String> result, char[] num, char[] num1, char[] num2, int index) {
        int left = index, right = num.length - 1 - index;

        if (left > right) {
            String s = String.valueOf(num);
            result.add(s);
            return;
        }

        if (left == right) {
            for (int i = 0; i < 3; i++) {
                num[left] = num1[i];
                dfs(result, num, num1, num2, index + 1);
            }
        } else {
            for (int i = 0; i < 5; i++) {
                if (index == 0 && i == 2) {
                    continue;
                }
                num[left] = num1[i];
                num[right] = num2[i];
                dfs(result, num, num1, num2, index + 1);
            }
        }
    } 
}

解法二：递归的方法，返回值不为空。 这种写法暂时还不是太熟，不能灵活运用。暂时的理解就是先处理base case，在这题里面就是left > right和left == right这两种情况。 然后递归的调用来更新解。

public class Solution {
    public List<String> findStrobogrammatic(int n) {
        if (n <= 0) {
            return new ArrayList<String>();
        }

        return helper(0, n - 1);
    }

    private List<String> helper(int left, int right) {
        if (left > right) {
            return new ArrayList<String>(Arrays.asList(""));
        } else if (left == right) {
            return new ArrayList<String>(Arrays.asList("0", "1", "8"));
        }

        List<String> list = helper(left + 1, right - 1);
        List<String> result = new ArrayList<String>();

        for (String s: list) {
            if (left != 0) {
                result.add("0" + s + "0");
            }
            result.add("1" + s + "1");
            result.add("8" + s + "8");
            result.add("6" + s + "9");
            result.add("9" + s + "6");
        }

        return result;
    }
}

Strobogrammatic Number III， 和第二题类似，遍历从low.length()到high.length()里的所有结果

public class Solution {
    public int strobogrammaticInRange(String low, String high) {
        char[] num1 = {'0', '1', '8', '9', '6'};
        char[] num2 = {'0', '1', '8', '6', '9'};

        int[] count = new int[1];
        for (int i = low.length(); i <= high.length(); i++) {
            char[] num = new char[i];
            dfs(num, num1, num2, low, high, count, i, 0);
        }

        return count[0];
    }

    private void dfs(char[] num, char[] num1, char[] num2, String low, String high, int[] count, int n, int index) {
        int left = index, right = num.length - 1 - index;
        if(left > right) {
            String now = String.valueOf(num);
            if (compare(low, now) && compare(now, high)) {
                count[0]++;
            }
            return;
        }

        if (left == right) {
            for (int i = 0; i < 3; i++) {
                num[left] = num1[i];
                dfs(num, num1, num2, low, high, count, n, index + 1);
            }
        } else {
            for (int i = 0; i < 5; i++) {
                if (left == 0 && i == 0) {
                    continue;
                }
                num[left] = num1[i];
                num[right] = num2[i];
                dfs(num, num1, num2, low, high, count, n, index + 1);
            }    
        }
    }

    private boolean compare(String low, String high) {
        long num1 = Long.parseLong(low);
        long num2 = Long.parseLong(high);

        return num1 <= num2;
    }
}

解法二： 递归，用hashmap尝试优化了一下，结果不对，这里有待再仔细看一下。 public class Solution { public int strobogrammaticInRange(String low, String high) { List result = new ArrayList();

    for (int length = low.length(); length <= high.length(); length++) {
        result.addAll(helper(length, length, low, high));
    }

    int count = 0;
    for (String s: result) {
        if (s.length() == low.length() && s.compareTo(low) < 0 || s.length() == high.length() && s.compareTo(high) > 0) {
            continue;
        }
        count++;
    }

    return count;
}

private List<String> helper(int current, int max, String low, String high) {
    if (current == 0) {
        return new ArrayList<String>(Arrays.asList(""));
    } else if (current == 1) {
        return new ArrayList<String>(Arrays.asList("0", "1", "8"));
    } 

    List<String> list = helper(current - 2, max, low, high);
    List<String> result = new ArrayList<String>();
    for (String s: list) {
        if (current != max) {
            result.add("0" + s + "0");
        }
        result.add("1" + s + "1");
        result.add("8" + s + "8");
        result.add("6" + s + "9");
        result.add("9" + s + "6");
    }

    return result;
}

}