字符串计数(动态规划)

本文主要是介绍字符串计数(动态规划)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。

输入描述:
每组数据包涵s1（长度小于100），s2（长度小于100），len1（小于100000），len2（大于len1，小于100000）

输出描述:
输出答案。

输入例子:
ab ce 1 2

输出例子:
56

刚看到这题的时候题目理解了半天，一开始理解错了字典序的意思，也是醉了，以为类似整数那样直接相减的算法（从右往左开始计算），后面才理解为字典序为（从左往右开始计算o(╯□╰)o），这个应该也是有点像动态规划的思想吧，先计算长度为len1然后计算len1+1、len1+2。。len2这样，记住每次的是26的（leni-1）次幂，类似于整数的高位数。详细的解题步骤如下：
首先要搞清楚字典序的意思：即从两个字符串的下标为0开始进行对比，字典序是从左往右进行对比的。
例如ab，abc这样两者之间的字符串个数为aba、abb，而ab、bb两者之间的字符串个数为：ac、ad、ae…az、ba这26个，所以高位的字符串个数要是26的i次幂。
其次，要理解题目的“长度在len1到len2的字符串的个数”，指的是长度在len1的字符串个数、长度在len1+1的字符串个数。。。长度为len2的字符串个数。
例abcde、acede这两个字符串，长度为1到4表示的是长度为1的时候两个字符a、a之间的个数，长度为2的时候两个字符ab、ac之间的个数，长度为3的时候abc、ace两个字符串之间的个数，长度为4：abcd、aced的个数。
所以计算的时候应该以长度作为变量遍历len1到len2之间的字符串个数，最后相加。

public static void main(String[] args) {// TODO Auto-generated method stubScanner scan = new Scanner(System.in);
//      String t[] = "a   b c".split(" ");
//      System.out.println((int)(0.6)+t.length);while(scan.hasNextLine()){String inputString[] = scan.nextLine().split(" ");System.out.println(getStrCount(inputString[0],inputString[1],Integer.parseInt(inputString[2]),Integer.parseInt(inputString[3])));//          System.out.println(scan.nextLine()+"@");}}/**** 求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。* @param str1 字符串s1* @param str2 字符串s2* @param len1 长度len1* @param len2 长度len1* @return 长度在len1到len2的字符串的个数，结果mod 1000007*/public static long getStrCount(String str1,String str2,int len1,int len2){
//      System.out.println(str1+" "+ str2+" "+len1+" "+len2);long sum = 0;char a[] = str1.toCharArray();char b[] = str2.toCharArray();int i = len1;for(i = len1; i <= len2; i++){//长度从len1 到len2，共有len2-len1种情况char a1 = a[0];char b1 = b[0];int t = b1 - a1;//两者的差值sum = sum + t * (long)Math.pow(26, i - 1);//先比较高位的差值，记得乘以26的i-1次幂long suma = 0,sumb = 0;//用于统计a[1]~a[i]的个数和b[1]~b[i]的个数，例a[1]-a[3] = abc 则每一位的个数分别为 123即a[1]-'a'-1=1,a[2]-'a'-1=2,a[3]-'a'-1=3int j = 1;int min = a.length > i ? i : a.length;for(j = 1; j < min; j++ ){t = a[j] - 'a' + 1;//算出其字典序的位置，所以是要剪掉'a'但还要加上一个1，例a的字典序为1，b的字典序为2suma = suma + t * (long)Math.pow(26, i - 1 - j);}min = b.length > i ? i : b.length;for(j = 1; j < min; j++ ){t = b[j] - 'a' + 1;sumb = sumb + t * (long)Math.pow(26, i - 1 - j);}sum = sum + sumb - suma;//sumb - suma 即剪掉a、b两个字符串从b[1]~b[i]的所有字符串的情况-a[1]~a[i]的所有字符串的情况即两者之间的字符串个数        }sum = sum - 1;//在计算最后一位的时候把字符串str2也包含进去了，所以要减去一个1，即题目给的例子计算ce的时候把ce计算进去了（b[1]-'a'+1的时候），所以要减掉一个1return sum % 1000007;}