String I

发表于   |  

Group Anagrams

#49 Group Anagrams

Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”],
Return:
[
[“ate”, “eat”,”tea”],
[“nat”,”tan”],
[“bat”]
]
Note:
For the return value, each inner list’s elements must follow the lexicographic order.
All inputs will be in lower-case.

思路：先将各个单词排序，排序后的字符串相同的单词即是anagrams。
具体实现需要用到容器HashMap，以键值对的形式保存排序后字符串相同的所有单词。key就是排序后字符串，value就是原本的单词组成的list。
e.g. (“abc”, [“abc”, “acb”, “bac”])

  • 遍历string数组，得到当前单词的顺序字符串，然后在HashMap中查找。
  • 若HashMap中已存在该key，则将该单词插入到对应的list中。
  • 若不存在，则新插入键值对。
    最后将Map中的list放入需要返回的表中。
    注意，因为题中要求list中的元素是有序的，所以要在最开始的时候将单词数组排序，以保证插入的顺序。 对容器的使用还不是很熟练啊~而且没有IDE，库函数好难记啊~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public List<List<String>> groupAnagrams(String[] strs) {
       //排序不能少，因为要保证最后结果是顺序的
       Arrays.sort(strs);
       Map<String, List<String>> map = new HashMap<String, List<String>>();
       for (int i = 0; i < strs.length; i++) {
           char[] c = strs[i].toCharArray();
           Arrays.sort(c);
           String s = String.valueOf(c);
           if (!map.containsKey(s)) 
               map.put(s, new ArrayList<String>());
           map.get(s).add(strs[i]);
       }
       return new ArrayList<List<String>>(map.values());
   }

Interleaving String

#97 Interleaving String

Given s1, s2, s3, find whether s3 is formed by the interleaving of s1 and s2.
For example,
Given:
s1 = “aabcc”,
s2 = “dbbca”,
When s3 = “aadbbcbcac”, return true.
When s3 = “aadbbbaccc”, return false.

要用到’dynamic programing’的思想。
若s1的前i个与s2的前j个对于s3的前(i+j)个来说是合法的(即这部分的s1和s2可以插入得到s3)，则可继续对s3的(i+j+1)个进行判断。

  • 最开始初始化i=0和j=0的情况为合法。
  • i=0即s1为空，只判断s2。
  • j=0即s2为空，只判断s1。
  • 都不为空，则s1或s2有一个合法即可。
  • 最后返回s1s2都插入后的结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean isInterleave(String s1, String s2, String s3) {
       int len1 = s1.length(), len2 = s2.length();
       if (s3.length() != len1 + len2)
           return false;
       boolean[][] dp = new boolean[len1+1][len2+1];
       for (int i = 0; i <= len1; i++) {
           for (int j = 0; j <= len2; j++) {
               if (i == 0 && j == 0)
                   dp[0][0] = true;
               else if (i == 0)
                   dp[i][j] = dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1);
               else if (j == 0)
                   dp[i][j] = dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1);
               else
                   dp[i][j] = (dp[i-1][j] && s1.charAt(i-1) == s3.charAt(i+j-1)) || (dp[i][j-1] && s2.charAt(j-1) == s3.charAt(i+j-1));
           }
       }
       return dp[len1][len2];
   }

Integer to English Words

#273 Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.
For example,
123 -> “One Hundred Twenty Three”
12345 -> “Twelve Thousand Three Hundred Forty Five”
1234567 -> “One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven”

大致分为(以前没注意，现在才发现歪果仁写数字总三个数隔一个逗号的用意。)：

"123" -> "One Hundred Twenty Three"
"123,000" -> "One Hundred Twenty Three Thousand"
"123,000,000" -> "One Hundred Twenty Three Million"
"123,000,000,000" -> "One Hundred Twenty Three Billion"

可以每三个数字转换，然后相应加上Thousand, Million, Billion。
注意要考虑一些特殊情况，比如’0’和’1000中的0’，’11’和’21’等。
考虑空格真是太麻烦了！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public final String[] digit = new String[] {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
   public final String[] tens = new String[] {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety", "Hundred"};
   public final String[] more = new String[] {"", " Thousand", " Million", " Billion"}; 
   
   public String numberToWords(int num) {
       if (num == 0)
           return digit[num];
       StringBuilder sb = new StringBuilder();
       int flag = 0;
       
       while (num > 0) {
           String temp = sb.toString();
           if (num % 1000 != 0) {
               StringBuilder t = new StringBuilder();
               t.append(inThreeDigit(num % 1000)).append(more[flag]);
               if (!temp.equals(""))
                   t.append(" ").append(temp);
               sb = t;
           }
           num = num / 1000;
           flag++;
       }
       return sb.toString();
   }
   
   public String inThreeDigit(int num) {
       StringBuilder sb = new StringBuilder();
       if (num < 20)
           sb.append(digit[num]);
       else if (num < 100) {
           sb.append(tens[num/10]);
           if (num % 10 != 0)
               sb.append(" ").append(digit[num%10]);
       }
       else  {
           sb.append(digit[num/100]).append(" Hundred");
           num %= 100;
           if (num < 20 && num != 0)
               sb.append(" ").append(digit[num]);
           else if (num != 0) {
               sb.append(" ").append(tens[num/10]);
               if (num % 10 != 0)
                   sb.append(" ").append(digit[num%10]);
           }
       }
       return sb.toString();
   }

吐槽：感觉关于字符串处理，很多是考的归纳能力，然后就着wrong answer打补丁。
这两天刷的有点乱，希望明天能有条理一点。