`
Wesleydeng
  • 浏览: 34779 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

一道算法题

 
阅读更多

 

今天在论坛上有这样的一道题目http://www.iteye.com/topic/15295
自己做了之后,也看看了一些别人的算法,发现跟其中一个人的差不多,所以就没有跟帖了,把自己的答案贴在了这里。
 题目:
假设有这样一种字符串,它们的长度不大于 26 ,而且若一个这样的字符串其长度为 m ,则这个字符串必定由 a, b, c ... z 中的前 m 个字母构成,同时我们保证每个字母出现且仅出现一次。比方说某个字符串长度为 5 ,那么它一定是由 a, b, c, d, e 这 5 个字母构成,不会多一个也不会少一个。嗯嗯,这样一来,一旦长度确定,这个字符串中有哪些字母也就确定了,唯一的区别就是这些字母的前后顺序而已。

现在我们用一个由大写字母 A 和 B 构成的序列来描述这类字符串里各个字母的前后顺序:

如果字母 b 在字母 a 的后面,那么序列的第一个字母就是 A (After),否则序列的第一个字母就是 B (Before);
如果字母 c 在字母 b 的后面,那么序列的第二个字母就是 A ,否则就是 B;
如果字母 d 在字母 c 的后面,那么 …… 不用多说了吧?直到这个字符串的结束。

这规则甚是简单,不过有个问题就是同一个 AB 序列,可能有多个字符串都与之相符,比方说序列“ABA”,就有“acdb”、“cadb”等等好几种可能性。说的专业一点,这一个序列实际上对应了一个字符串集合。那么现在问题来了:给你一个这样的 AB 序列,问你究竟有多少个不同的字符串能够与之相符?或者说这个序列对应的字符串集合有多大?注意,只要求个数,不要求枚举所有的字符串。

 

   分析:

   由于后一个字母可以放置的位置与前一个字母放置的位置preAlphabetPosition有关,用递归法可以得到答案

 

   我的解法:

 

public class CountAllPossible
{
	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		// TODO Auto-generated method stub
		int sum=countAllPossible("ABA");
		System.out.println(sum);
	}
	
	public static int countAllPossible(String str)
	{
		return count(str,0,1);
	}
	
	public static int count(String subStr,int preAlphabetPosition,int allPossiblePosition)
	{
		if(subStr.charAt(0)!='A'&&subStr.charAt(0)!='B')
			throw new IllegalArgumentException();
		
		int sum=0;
		if(subStr.charAt(0)=='A')
		{
			for (int index = 0; index <= preAlphabetPosition; index++)
			{
				if(subStr.length()==1)
				{
					sum+=1;//reach the end 
				}
				else
				{
					sum+=count(subStr.substring(1),index,allPossiblePosition+1);
				}
			}
		}
		else//='B'
		{
			for(int index=preAlphabetPosition+1;index<=allPossiblePosition;index++)
			{
				if(subStr.length()==1)//reach the end
				{
					sum+=1;
				}
				else
				{
					sum+=count(subStr.substring(1),index,allPossiblePosition+1);
				}
			}
			
		}
		return sum;
	}

}
 

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics