首页 > 代码库 > Letter Combinations of a Phone Number [leetcode]谈谈循环解法的两种思路
Letter Combinations of a Phone Number [leetcode]谈谈循环解法的两种思路
本系列博文中有很多两种思路的,其实是因为第一遍刷题的时候有一个想法,第二遍刷题的时候已经忘掉之前的思路了,又有新的想法了。
同时大部分代码我也同时PO到leetcode的对应题目的问答中去了,所以如果你也查看问题讨论的话会发现有和我一模一样的代码,其实就是我PO的:)
书接正文,基于循环的两种思路如下:
第一种思路
比如“234”这个字符串,我可以先将0...1的所有排列找到-->{"a", "b", "c"}
再进一步将0...2的所有排列找到-->{"ad", "ae","af", "bd", "be", "bf", "cd", "ce", "cf"}
如此循环...直到字符串末尾。实现如下
vector<string> letterCombinations(string digits) { vector<string> res; string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; res.push_back(""); for (int i = 0; i < digits.size(); i++) { vector<string> tempres; string chars = charmap[digits[i] - '0']; for (int c = 0; c < chars.size();c++) for (int j = 0; j < res.size();j++) tempres.push_back(res[j]+chars[c]); res = tempres; } return res; }
先生成"234"的第一个可行解"adg",再在可行解上衍生出其他解
类似数数的时候遇到9就变成0并进位
vector<string> letterCombinations(string digits) { string charmap[10] = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; vector<string> res; string alpha; for (int i = 0; i < digits.size(); i++) alpha += charmap[digits[i] - '0'][0]; while (true) { res.push_back(alpha); //寻找可行解 bool find = false; for (int i = digits.size() - 1; i >= -1 && ! find; i--) { if (i == -1) return res;//遍历结束 string chars = charmap[digits[i] - '0']; if (alpha[i] == chars[chars.size() - 1])//遍历第i个数字的最后一个可行解,重置并寻找第i+1个数字的可行解 { alpha[i] = chars[0]; continue; } for (int c = 0; c < chars.size() && ! find; c++)//遍历第i个数字的其他可行解 { if (alpha[i] == chars[c]) { alpha[i] = chars[c+1]; find = true; } } } } }
Letter Combinations of a Phone Number [leetcode]谈谈循环解法的两种思路
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。