String例题分析

-- ZigZag Convertion

    >> 题目：给定一个字符串和n（代表zigzag的高度），输出zigzag以后的字符串

    >> 地址：

    >> 解题思路：就是简单的转换了。注意特殊情况处理

-- word latter II

    >> 题目：给定两个单词和一个词典，输出所有可能从单词1到单词2的路径

    >> 解题思路：广度优先搜索并记录路径，但是由于要输出路径，所以要记录，只用广度优先，至少内存开销会很大。继续深挖题目信息，就算是所有最短路径，那么每个单词也只会出现一次，所有只要继续

    private void bfs(String start, String end, Set<String> dict, Map<String, Integer> depthMap) {
        // define
        Queue<String> visiting, nextVisiting, tempQ;
        Set<String> visited;
        char c = 'a';
        int depth;

        // init
        visiting = new LinkedList<String>();
        nextVisiting = new LinkedList<String>();
        visited = new HashSet<String>();
        depth = 2;

        // cal
        visited.add(start);
        visiting.add(start);
        depthMap.put(start, 1);
        while (!visiting.isEmpty()) {
            String item = visiting.poll();

            if (item.equals(end)) {
                return;
            }

            char []cs = item.toCharArray();
            for (int i = 0; i < item.length(); i++) {
                for (c = 'a'; c <= 'z'; c++) {
                    if (cs[i] == c) {
                        continue;
                    }
                    cs[i] = c;
                    String temp = new String(cs);
                    if (dict.contains(temp) && !visited.contains(temp)) {
                        nextVisiting.add(temp);
                        visited.add(temp);
                        depthMap.put(temp, depth);
                    }
                    cs[i] = item.charAt(i);
                }
            }

            if (visiting.isEmpty()) {
                tempQ = nextVisiting;
                nextVisiting = visiting;
                visiting = tempQ;
                depth++;
            }
        }
    }

    private void dfs(String start, String end, Set<String> dict, Map<String, Integer> depthMap, List<String> path, List<List<String>> result) {
        // define
        List<String> newPath;
        char c = 'a';
        int depth;

        // init

        //special
        if (start.equals(end)) {
            path.add(end);
            result.add(path);
            return;
        }
        if (!depthMap.containsKey(start)) {
            return;
        }
        path.add(start);
        depth = depthMap.get(start);
        char []cs = start.toCharArray();
        for (int i = 0; i < start.length(); i++) {
            for (c = 'a'; c <= 'z'; c++) {
                if (c == cs[i]) {
                    continue;
                }
                cs[i] = c;

                String temp = new String(cs);
                if (depthMap.containsKey(temp) && depthMap.get(temp) == depth + 1) {
                    newPath = new ArrayList<String>(path);
                    dfs(temp, end, dict, depthMap, newPath, result);
                }
                cs[i] = start.charAt(i);
            }
        }

    }

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // define
        List<List<String>> result = new ArrayList<List<String>>();
        Map<String, Integer> depthMap = new HashMap<String, Integer>();
        List<String> path = new ArrayList<String>();

        // special
        if (start == null || end == null) {
            return result;
        }

        // init

        // cal
        bfs(start, end, dict, depthMap);
        dfs(start, end, dict, depthMap, path, result);

        // ret
        return result;
    }

-- Wildcard Matching    

    >> 题目：实现通配符模式匹配，包括对？和*的支持

'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

    >> 地址：

    >> 解题思路：模式串中会出现三种字符，然后对于java 的处理，在最后添加一位标志位。

            ++ 对于？字符，直接匹配，后移

            ++ 对于普通字符，直接匹配，如果之前没有'*'，可以使用最简单的来处理；如果之前已经出现了'*'，而且没有匹配上，则从最后一个'*'后（模式串） 与 第一次碰到最后一块'*'的位置后移一位开始匹配（原字符串的某个位置），每次遇到匹配不上，将将原字符串中的记录位置后移一位，然后与模式串最后'*'后面的字符进行匹配。

    public boolean isMatch(String s, String p) {
        int i = 0, j = 0, tempI = 0, tempJ = 0;
        boolean firstFlag = true;
        String ss = s + '\0', pp = p + '\0';
        for (i = 0, j = 0; ss.charAt(i) != '\0'; i++, j++) {
            switch(pp.charAt(j)) {
            case '?':
                break;
            case '*':
                firstFlag = false;
                tempI = i;     // record the index
                tempJ = j;
                while (pp.charAt(tempJ) == '*') tempJ++; //skip continuous '*'
                i = tempI - 1; // back one position to rematch;
                j = tempJ - 1; // last '*'
                break;
            default:
                if (ss.charAt(i) != pp.charAt(j)) {
                    if (firstFlag) return false;
                    tempI++; // there is a '*' before this j
                    i = tempI - 1;
                    j = tempJ - 1;
                }
            }
        }
        while (pp.charAt(j) == '*') j++;
        return pp.charAt(j) == '\0';
    }

-- Valid Parentheses

    >> 题目：给定一个字符串，判断是否括号匹配

    >> 解题思路：使用栈，对于暂时没有匹配上的先入栈，匹配上的出栈，遍历完判断即可。

-- Valid Palindrome

    >> 题目：给定一个字符串，判断其是否是回文。

    >> 解题思路：注意需要处理掉特殊字符，然后根据前后两个index来判断。

-- Valid Number

    >> 题目：给定一个字符串，判断其是否是一个数字

    >> 解题思路：有限状态机

-- Text Justification     

    >> 题目：文本对齐，给定一个数组和长度L，使字符串对齐。    You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly L characters.    Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

    >> 解题思路：

-- Substring with Concatenation of All Words

    >> 题目：

-- String to Integer(atoi)

    >> 题目：给定一个字符串，将其转换为int

    >> 解题思路：主要是异常处理，空格处理，可能是负数（- +处理），可能超出int的范围

    int atoi(const char *str) {
        int ret = 0, i = 0, len = strlen(str), flag = 1, num = 0;
        long long tmp = 0;
        for (i = 0; i < len && str[i] == ' '; i++) ;
        if (i == len) return 0;
        if (str[i] == '-') flag = -1;
        if (str[i] == '-' || str[i] == '+') i++;
        for ( ; i < len && (str[i] >= '0' && str[i] <= '9'); i++) {
            num = str[i] - '0';
            tmp = tmp * 10 + num;
        }
        if (tmp >= 2147483647 && flag == 1)
            ret = 2147483647;
        else if (tmp > 2147483648 && flag == -1)
            ret = 2147483648;
        else
            ret = tmp;
        ret *= flag;
        return ret;
    }

-- Simplify Path

    >> 题目：给定一个unix路径，对其进行简化

    >> 地址：

    >> 解题思路：利用list模拟stack和queue。

    public String simplifyPath(String path) {
        List<String> queue = new ArrayList<String>();
        if (path.length() == 1) return path;
        int i = 0, j = 1;
        String paths = path + '/';
        String temp = null;
        for (i = 0, j = 1; j < paths.length(); ) {
            if (paths.charAt(j) == '/') {
                temp = paths.substring(i, j);
                if (temp.equals("/.")) {

                } else if (temp.equals("/")) {

                } else if (temp.equals("/..")) {
                    if (queue.size() > 0) {
                        queue.remove(queue.size() - 1);
                    }
                } else {
                    queue.add(temp);
                }
                i = j;
                j++;
            } else {
                j++;
            }
        }
        StringBuilder sb = new StringBuilder("");
        for (String str : queue) {
            sb.append(str);
        }
        if (sb.length() == 0) {
            sb.append("/");
        }
        return sb.toString();
    }