Code & Fun

打卡,第13天

昨晚贼晚睡,然后今天就快吃午饭才起来,然后我又躺尸了一个下午。。。

今天刷了一道Medium的题目—— Letter Combinations of a Phone Number,不过感觉好水,就和学校oj一样水。。。

Given a digit string, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string “23”
Output: [“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].
Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

恩,大概思路就是要求letterCombinations(digits),我们就需要求letterCombinations(digits.substr(0,n-1).

然后把这个思路转换迭代的方式就成了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<string> letterCombinations(string digits) {
static vector<string> sMap {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
vector<string> ret;
if (digits.size() == 0) return ret;
ret.push_back("");
for(int i = 0;i < digits.size();i++) {
vector<string> now;
for(auto c:sMap[digits[i] - '0']) {
for(auto s:ret)
now.push_back(s+c);
}
ret.swap(now);
}
return ret;
}

思路很简单,实现起来也很简单,没什么好提的,而且dicuss中的思路也很这个差不多,不过还是总结一下吧:

  • c++ 中 charstring真心麻烦:

    • stringstream很优雅,但是也很麻烦,而且只适用于要平凡从尾部插入的情况,不过这个方法结合io可以做很多漂亮的转换
    • "" + c,之前的时候用的时候好像是可以的,但是刚才在做题的时候是不行的会出现一些奇怪的字符串。
    • 最后是比较简单,可以常用的方法:string(1,c),可以把1换成其他数字以获取有重复字符的字符串。
  • 然后是在dicuss中看到的vectorswap方法,有些情况应该还是不错的,可以提高效率,它应该是直接交换底层指针。


本文首发于Code & Fun