题解 | #字符串计数#
字符串计数
https://www.nowcoder.com/practice/f72adfe389b84da7a4986bde2a886ec3
题目描述
求字典序在 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);
}
}
}
投递博世等公司7个岗位
盒马一面2人在聊
查看3道真题和解析