5/24 String 杂题

今天脑洞开的有点大，写点水题压压惊。。

Valid Parentheses

我发现当输入情况就那么几个的时候，用 switch case 是个省事的好办法。。可以直接把 hashmap 都省了。

public class Solution {
    public boolean isValid(String s) {
        if(s.length() == 0) return true;
        Stack<Character> stack = new Stack<Character>();

        for(int i = 0; i < s.length(); i++){
            char chr = s.charAt(i);
            if(stack.isEmpty()){
                stack.push(chr);
            } else {
                if(chr=='(' || chr=='[' || chr == '{'){
                    stack.push(chr);
                } else {
                    if(getPair(chr) == stack.peek()){
                        stack.pop();
                    } else {
                        return false;
                    }
                }
            }
        }

        return stack.isEmpty();
    }

    private char getPair(char chr){
        switch(chr){
            case ')':
                return '(';
            case ']':
                return '[';
            case '}':
                return '{';
            default:
                return '.';
        }
    }
}

Longest Common Prefix

自己匆忙写的，有点挫。

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length == 0) return "";

        StringBuilder sb = new StringBuilder();
        int index = 0;
        int maxLength = 0;
        for(int i = 0; i < strs.length; i++){
            maxLength = Math.max(maxLength, strs[i].length());
        }

        while(index < maxLength){
            if(index == strs[0].length()) return sb.toString();
            char chr = strs[0].charAt(index);
            for(int i = 0; i < strs.length - 1; i++){
                String cur = strs[i];
                String next = strs[i+1];

                if(index == cur.length() || index == next.length()){
                    return sb.toString();
                }
                if(cur.charAt(index) != next.charAt(index)){
                    return sb.toString();
                }
            }
            sb.append(chr);
            index ++;
        }


        return sb.toString();
    }
}

论坛上好一点的写法：

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length < 1 || strs == null) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        //find the shortest String
        int shortest = 0;
        int len = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            int curLen = strs[i].length();
            if (curLen < len) {
                len = curLen;
                shortest = i;
            }
        }
        //find the longest common prefix
        String sub = strs[shortest];
        for (int i = 0; i < strs.length; i++) {
            while (strs[i].indexOf(sub) != 0) {
                sub = sub.substring(0, sub.length()-1);
            }
        } 
        return sub;
    }
}

• 当问题非常简单的时候，解题重点就从优化时间复杂度变成了优化代码简洁性。

Group Anagrams

比较 Trivial 的问题，没啥特别好说的。。

这题主要的乐趣在于怎么把多个是 anagram 的 string 映射到同一个 key 上。简单的办法是排序，或者开个 int[] 统计字母数量，然后生成一个类似于 1a2b4f 这种的 string signature.

除此之外比较 fancy 的写法是利用 prime number 做 string hashing，容错率不太好而且我觉得用 prime number 总是要去证明一下算法的正确性，不太适用于面试。

public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> rst = new ArrayList<List<String>>();
        if(strs == null || strs.length == 0) return rst;

        HashMap<String, List<String>> map = new HashMap<String, List<String>>();

        for(String str : strs){
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String sortedStr = new String(array);

            if(!map.containsKey(sortedStr)){
                List<String> list = new ArrayList<String>();
                list.add(str);
                map.put(sortedStr, list);
            } else {
                map.get(sortedStr).add(str);
            }
        }

        for(String str : map.keySet()){
            // OJ wants each list to be sorted
            Collections.sort(map.get(str));
            rst.add(map.get(str));
        }

        return rst;
    }
}

Length of Last Word

简直惊了。。这题有难度吗。。

public class Solution {
    public int lengthOfLastWord(String s) {
        int length = 0;
        for(int i = s.length() - 1; i >= 0; i--){
            if(s.charAt(i) == ' ') continue;
            while(i >= 0 && s.charAt(i) != ' '){
                length ++;
                i --;
            }
            break;
        }

        return length;
    }
}