描述:

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.

思路:

本题目要实现的效果就是产生一系列广义有序的字符串序列,本来想假如知道digits字符串长度的话,可以搞一个n层循环,但是digits的长度是未知的。想了好久,想到了用递归来实现本题目要实现的功能,每个数字循环到数字所代表字符的个数大小时,返回上一级递归,然后再在上一级的循环层次计数上再加1即可。

当字符的长度等于digits的长度时,说明已经产生一组有效的字符串,存储起来,然后将最后一个字符删除,继续循环。。。。

最后,当index<0时,说明整个循环已经结束,over!但是在具体实现的过程中,递归理解起来比较复杂,具体如何结束,这个判断条件需要特别注意下,假如只是简单的return可能达不到应有的效果。

总之,这题目搞了两个多小时,感觉有点乱。

代码:

boolean flag=true;
	int digitsLength=0;
	int arr[];
	List<String>list=new ArrayList<String>();
	StringBuilder sBuilder=new StringBuilder();
	Map<Integer, String>map=new HashMap<Integer, String>();
	public List<String> letterCombinations(String digits) {
		if(digits==null||digits.length()==0)
			return list;
        digitsLength=digits.length();
        arr=new int[digitsLength];
        int digitsArr[]=new int[]{2,3,4,5,6,7,8,9};
        String strArr[]=new String[]{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        int len=digitsArr.length;
        Arrays.fill(arr, 0);
        for(int i=0;i<len;i++)
        	map.put(digitsArr[i], strArr[i]);//数字对应的字符
        combinations(digits,0);
        return list;
    }
	public void combinations(String digits,int index)
	{
		if(!flag)//flag为false时彻底结束
			return;
		if(index<0)
		{
			flag=false;//index<0时彻底结束
			return;
		}
		int number=digits.charAt(index)-'0';
		String string=map.get(number);//获得数字对应的字符
		int len=string.length();
		int upLevelIndex=0;
		if(index<digitsLength-1)//还没有达到有效字符的长度
		{
			if(arr[index]==len)//达到该数字对应字符的最大值
			{
				arr[index]=0;
				upLevelIndex=sBuilder.length()-1;//向上面一层循环前,先把上面一层那个数字对应的字符删去
				if(upLevelIndex>=0)
				{
					sBuilder.deleteCharAt(upLevelIndex);
					combinations(digits,index-1);
				}else {
					flag=false;//到达最前面
					return;
				}
			}else{
				sBuilder.append(string.charAt(arr[index]));
				arr[index]++;
				combinations(digits,index+1);
			}
		}
		else//达到有效字符串的长度
		{
			for(int i=0;i<len;i++)
			{
				sBuilder.append(string.charAt(i));
				list.add(sBuilder.toString());//保存结果
				sBuilder.deleteCharAt(sBuilder.length()-1);//删除最后一个字符,继续循环
			}
			upLevelIndex=sBuilder.length()-1;//向上面一层循环前,先把上面一层那个数字对应的字符删去
			if(upLevelIndex>=0)
			{
				sBuilder.deleteCharAt(upLevelIndex);
				combinations(digits,index-1);
			}else {
				flag=false;//到达最前面
				return;
			}
			
		}
	}

结果:


Logo

开放原子开发者工作坊旨在鼓励更多人参与开源活动,与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动,如meetup、训练营等,主打技术交流,干货满满,真诚地邀请各位开发者共同参与!

更多推荐