当前位置:网站首页>【Hot100】17. Letter combination of telephone number
【Hot100】17. Letter combination of telephone number
2022-07-01 16:05:00 【Wang Liuliu's it daily】
17. Letter combination of telephone number
Reference resources :https://leetcode.cn/problems/letter-combinations-of-a-phone-number/solution/tong-su-yi-dong-dong-hua-yan-shi-17-dian-hua-hao-m/
- to flash back
Recursive calls are nested in the loop
There is a small detail in the code implementation , If it is pure string splicing , Many temporary objects will be generated , The performance will be slightly worse ,Java In the implementation, we use StringBuilder Spliced , Tested time consuming 0 millisecond , If it is to use String It takes time for type splicing 6 millisecond .
class Solution {
// A mapping table , The second position is "abc“, The third position is "def"...
// It can also be used here map, Using arrays can save more memory
String[] letter_map = {
" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
// Pay attention to the boundary conditions
if(digits==null || digits.length()==0) {
return new ArrayList<>();
}
iterStr(digits, new StringBuilder(), 0);
return res;
}
// The final output is list
List<String> res = new ArrayList<>();
// Recursive function
void iterStr(String str, StringBuilder letter, int index) {
// The termination condition of recursion , Note that the termination conditions here look a little different from the dynamic demo , It is mainly optimized
// The dynamic graph is a part of each intercepted string ,"234", become "23", And then become "3", Finally become "", It doesn't perform well
// While using index Record the position of each traversal to the string , It's better
if(index == str.length()) {
res.add(letter.toString());
return;
}
// obtain index The character of position , Suppose the input character is "234"
// The first time you recurs index by 0 therefore c=2, The second time index by 1 therefore c=3, third time c=4
//subString Each time a new string is generated , and index Is to take the current character , So be more efficient
char c = str.charAt(index);
//map_string The following table is from 0 Start all the way to 9, c-'0' You can get the relative array subscript position
// such as c=2 When ,2-'0', Get the subscript as 2,letter_map[2] Namely "abc"
int pos = c - '0';
String map_string = letter_map[pos];
// Traversal string , For example, the first time I got 2, Page is traversal "abc"
for(int i=0;i<map_string.length();i++) {
// Call the next level of recursion , It is difficult to describe in words , Please understand with dynamic diagram
letter.append(map_string.charAt(i));
// If it is String The splicing efficiency of type will be relatively low
//iterStr(str, letter+map_string.charAt(i), index+1);
iterStr(str, letter, index+1);
letter.deleteCharAt(letter.length()-1);
}
}
}
- queue
You can take advantage of the first in, first out feature of queues , Then cooperate with the cycle
class Solution {
public List<String> letterCombinations(String digits) {
if(digits==null || digits.length()==0) {
return new ArrayList<String>();
}
// A mapping table , The second position is "abc“, The third position is "def"...
// It can also be used here map, Using arrays can save more memory
String[] letter_map = {
" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};
List<String> res = new ArrayList<>();
// First, add a null character to the queue
res.add("");
for(int i=0;i<digits.length();i++) {
// Characters traversed by the current , Find the corresponding string in the dictionary table
String letters = letter_map[digits.charAt(i)-'0'];
int size = res.size();
// After calculating the queue length , Take out each element in the queue one by one
for(int j=0;j<size;j++) {
// Take the first element out of the queue every time
String tmp = res.remove(0);
// Then follow "def" Such string splicing , And put it in the queue again
for(int k=0;k<letters.length();k++) {
res.add(tmp+letters.charAt(k));
}
}
}
return res;
}
}
边栏推荐
- 软件测试的可持续发展,必须要学会敲代码?
- The picgo shortcut is amazing. This person thinks exactly the same as me
- Pico, can we save consumer VR?
- Problems encountered in IM instant messaging development to maintain heartbeat
- I'm a senior test engineer who has been outsourced by Alibaba and now has an annual salary of 40w+. My two-year career changing experience is sad
- ATSs: automatically select samples to eliminate the difference between anchor based and anchor free object detection methods
- 运动捕捉系统原理
- 【Hot100】19. 删除链表的倒数第 N 个结点
- How does win11 set user permissions? Win11 method of setting user permissions
- 2023 spring recruitment Internship - personal interview process and face-to-face experience sharing
猜你喜欢
MySQL的零拷贝技术
Malaysia's Star: Sun Yuchen is still adhering to the dream of digital economy in WTO MC12
Automatic, intelligent and visual! Deeply convinced of the eight designs behind sslo scheme
圈铁发音,动感与无噪强强出彩,魔浪HIFIair蓝牙耳机测评
Hardware development notes (9): basic process of hardware development, making a USB to RS232 module (8): create asm1117-3.3v package library and associate principle graphic devices
Introduction to RT thread env tool (learning notes)
ADS算力芯片的多模型架构研究
从 MLPerf 谈起:如何引领 AI 加速器的下一波浪潮
动作捕捉系统用于苹果采摘机器人
idea启动Command line is too long问题处理
随机推荐
近半年内连获5家“巨头”投资,这家智能驾驶“黑马”受资本追捧
2023届春招实习-个人面试过程和面经分享
Nuxt.js数据预取
ssm框架原理
电脑照片尺寸如何调整成自己想要的
How to write good code - Defensive Programming Guide
The newly born robot dog can walk by himself after rolling for an hour. The latest achievement of Wu Enda's eldest disciple
Pico, do you want to save or bring consumer VR?
Automatique, intelligent, visuel! Forte conviction des huit conceptions derrière la solution sslo
Zero copy technology of MySQL
Go语学习笔记 - gorm使用 - 表增删改查 | Web框架Gin(八)
Idea start command line is too long problem handling
部门来了个拿25k出来的00后测试卷王,老油条表示真干不过,已被...
MySQL的零拷贝技术
【LeetCode】43. String multiplication
[daily news]what happened to the corresponding author of latex
What time do you get off work?!!!
Research on multi model architecture of ads computing power chip
Vscode find and replace the data of all files in a folder
Hardware development notes (9): basic process of hardware development, making a USB to RS232 module (8): create asm1117-3.3v package library and associate principle graphic devices