题目描述
求字典序在 s1 和 s2 之间的,长度在 len1 到 len2 的字符串的个数,结果 mod 1000007。数据范围:1 <= len(s1),len(s2) <= 50 ,1 <= len1,len2 <= 50
注意:本题有多组输入
输入描述:
每组数据包涵s1(长度小于50),s2(长度小于50),len1(小于50),len2(大于len1,小于50)
输出描述:
输出答案。
示例1
输入:
题意理解:
ab ce 1 2
输出:
56
每组数据输入两个字符串 s1 和 s2 ,这两个字符串的长度之间没有关系,长度范围在1到50之间。另外输入两个长度数值 len1 和len2 ,这两个长度之间也没有关系,并且这两个长度值和字符串的长度值也没有关系, 值在1到50之间。要求在len1到 len2长度,按照字典序求出s1 到s2之间的字符串个数(注意是之间,不包括s1和s2两个原串)。这个题意读完容易懵,这很正常,举例解释, s1 是 ab ,s2是ce,len1 是1,len2 是2,那么按照字典序,长度为1时,符合的字符串只有 b和c ,如果不好理解,你可以把单个的b理解为bb,c理解为cc ,所以ab 到ce的单个字符串 只有b和c ,而没有a,因为a理解为aa,它小于ab,就不在这个范围内。 然后说长度为2时,也就是 len2,ab到ce之间,有ac,ad,ae。。。az(这是24个),bb,bc,bd。。bz(这是26个),ca,cb,cc,cd(这是4个)。所以len2长度,有54个字符串,而len1有2个,所以总共有56个字符串。上面我们说的是len的长度不超过字符串的长度,那如果s1是abb,s2是ce,len1是1,len2是3如何处理呢? 答案是 添加长度,以len2为标准,s1的长度正好是3,不添加,s2长度是2,给它添加一个,添加 'z'+1 。为什么呢, 我们计算的时候按位数直接相减, 比如len为2时,ce 减ab ,结果就是 2 和3 ,这里应该能理解。 由上面计算可知,len为2时,十进制差1,字符串个数差26,比如 ab到bb之间有26个字符串(这里包含了bb),ab到cb之间有2*26=52 个字符串(包含了cb),那么ab到ce之间应该有2*26+(5-2)=55 个(包含了ce),但是题意要求不能包含边界,所以要把边界去掉,就是最后的结果减一。最后一个问题,为什么是 'z'+1,因为如果s1是ab,s2是bb,len2是3,补位 s1 是 aba,s2是bbz,如果直接按照上面的计算逻辑,bbz会被jian'd 这也就是我们之后的解题思路。现在你应该是理解题意了。那我们看下代码,就很容易懂了!
import java.util.*; public class Main{ public static void main(String[] args){ Scanner scan = new Scanner(System.in); while(scan.hasNext()){ String s1 =scan.next(); String s2 = scan.next(); int len1 =scan.nextInt(); int len2 = scan.nextInt(); // 先拿到s1的长度,如果小于len2,就给它补相应的位数,由于它是起始位,所以补a for(int i=s1.length();i<len2;i++){ s1 +='a'; } // 拿到s2的长度,如果小于len2,也给它补相应的位数,由于它是结束位,所以补'z'+1 for(int i=s2.length();i<len2;i++){ s2+='z'+1; } // 用一个数组,记录两个字符串对应位相减的值, 比如s1补位后为 aba,s2补位后为 ce('z'+1),arr数组记录的值是 {2,3,26} int[] arr = new int[len2]; // 由于下标比长度小1,所以是取不到len2的 for(int i=0;i<len2;i++){ arr[i] = s2.charAt(i)-s1.charAt(i); } // 用一个变量记录总的数值 int sum = 0; // 从长度len1开始,依次计算每个长度下的字符串个数,这里能取到len2 for(int i= len1;i<=len2;i++){ // 每个长度下,都从arr数组中取值,让它乘以相应的26的次方,比如数组中是{2,3},len为2时,就是2*Math.pow(26,1)+3*Math.pow(26,0)。 // len为3时,就是 2*Math.pow(26,2)+3*Math.pow(26,1) for(int j=0;j< i;j++){ // 次方既受 len的影响,也受位数的影响,所以是 i-j-1 sum+=arr[j]* Math.pow(26,i-1-j); } } System.out.println((sum-1)%1000007); } } }