Saturday, June 8, 2013

Phone number combinations @leetcode

刷题必备书籍Cracking the Coding Interview: 150 Programming Questions and Solutions 

简历:The Google Resume: How to Prepare for a Career and Land a Job at Apple, Microsoft, Google, or any Top Tech Company
算法学习书籍:Introduction to Algorithms
编程珠玑:Programming Pearls (2nd Edition)
C++ 学习:The C++ Programming Language, 4th Edition
经典操作系统书籍,龙书:Operating System Concepts
创业:The Start-up of You: Adapt to the Future, Invest in Yourself, and Transform Your Career
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.

class Solution {
public:
vector<string> letterCombinations(string digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
const string dict[] = {"","","abc","def","ghi","jkl","mno","qprs","tuv","wxyz"};
vector<string> ans;
ans.push_back("");
for(int i=0;i<digits.length();i++) {
const string s = dict[digits[i]-'0'];
vector<string> tmp;
for(int j=0;j<s.length();j++) {
for(int k=0;k<ans.size();k++) {
tmp.push_back(ans[k]+string(1,s[j]));
}
}
ans = tmp;
}
return ans;
}
};

No comments:

Post a Comment

Leetcode 316. Remove Duplicate Letters

 这道题表面问的是如何删除重复,实际在问如何从多个字符选取一个保留,从而让整个字符串按升序排列。那么策略就是对于高顺位的字符比如‘a',就要选靠前位置的保留,而低顺位字符如’z'则应该尽量选取靠后位置保留。 算法大概思路:每看到一个字符,我们要决定是否保留 1. ...