LeetCode 문제 풀이 day 017 (Jieky)

24276 단어 LeetCodeleetcode자바
LeetCode 17 번 문제
/*
Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

2 abc
3 def
4 ghi
5 jkl
6 mno
7 pqrs
8 tuv
9 wxyz

Example:
Input: "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.
*/

import java.util.*;
public class LetterCombinationsPhoneNumber{
     
	public static void main(String[] args){
     
		String str = "23";
		LetterCombinationsPhoneNumber lcpn = new LetterCombinationsPhoneNumber();
		List<String> result = lcpn.letterCombinations03(str);
		System.out.println(result);
	}
	
	//     ,     add List 
	public List<String> letterCombinations03(String digits) {
     
		// Given a string containing digits from 2-9 inclusive
		
		//   LinkedList,          
		List<String> ret = new ArrayList<>();
		if (digits == null || digits.length() == 0) return ret;
		
		String[] strs = {
     "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
		
		//                ,    ""
		combination(ret,digits,strs,0,"");
		
		return ret;
	}
	private void combination(List<String> ret,String digits,String[] strs,int index,String prefix){
     
		//     
		if(index == digits.length()){
     
			//       ,     ,        List
			ret.add(prefix);
			return; 
		}
		
		// String temp = strs[Integer.parseInt(digits.substring(index,index+1)) - 2];
		String temp = strs[Character.getNumericValue(digits.charAt(index)) - 2];
		//         
		for (int i=0;i<temp.length();i++){
     
			combination(ret,digits,strs,index+1,prefix+temp.substring(i,i+1));
		}
	}
	
	//   ,    
	public List<String> letterCombinations02(String digits) {
     
		// Given a string containing digits from 2-9 inclusive
		
		//   LinkedList,          
		LinkedList<String> ret = new LinkedList<>();
		if (digits == null || digits.length() == 0) return ret;
		
		String[] strs = {
     "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
		
		//   for         ,               
		ret.add("");
		for (int i=0;i<digits.length();i++){
     
			// Integer.parseInt       ,      
			// Character.getNumericValue        
			String temp = strs[Character.getNumericValue(digits.charAt(i)) - 2];
			//      LinkedList   。ret.add("")    ret      1,  if  。
			int len = ret.size();
			for (int j = 0;j < len;j++){
     
				//            
				String getStr = ret.removeFirst();
				for (int k=0;k<temp.length();k++){
     
					//           
					ret.addLast(getStr+temp.substring(k,k+1));
				}
			}
		}
		return ret;
	}
	
	public List<String> letterCombinations01(String digits) {
     
		// Given a string containing digits from 2-9 inclusive
		List<String> ret = new ArrayList<>();
		if (digits == null || digits.length() == 0) return ret;
		
		String[] strs = {
     "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; 
		
		for (int i=0;i<digits.length();i++){
     
			// Integer.parseInt       ,      
			String temp = strs[Integer.parseInt(digits.substring(i,i+1)) - 2];
			
			if (ret.size() > 0){
     
				//     ret   ,             
				List<String> ret_temp = new ArrayList<>();
				for (String p:ret){
     
					for (int j=0;j<temp.length();j++){
     
						ret_temp.add(p+temp.substring(j,j+1));
					}
				}
				//   List
				ret = ret_temp;
			}else{
     
				//              ret
				for (int j=0;j<temp.length();j++){
     
					ret.add(temp.substring(j,j+1));
				}
			}
			
		}
		return ret;
	}
}

좋은 웹페이지 즐겨찾기