美团字典序笔试题

<span style="color: rgb(51, 51, 51); font-family: arial, STHeiti, 'Microsoft YaHei', 宋体; font-size: 14px; line-height: 19.6px;">求字典序在s1和s2之间的，长度在len1到len2的字符串的个数，结果mod 1000007。</span>
           

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] input = sc.nextLine().split(" ");
            String str1 = input[0];
            String str2 = input[1];
            int min = Integer.parseInt(input[2]);
            int max = Integer.parseInt(input[3]);

            long sum1 = 0;
            long sum2 = 0;
            for (int i = min; i <= max; ++i) {
                sum1 += pos(str1, i);
                sum2 += pos(str2, i);

            }
            System.out.println(sum2 - sum1 - 1);
        }
        sc.close();
    }

    public static long pos(String s, int len) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] chs = s.toCharArray();
        long pre = 0;
        long res = 0;
        if (s.length() <= len) {
            for (int i = 0; i < s.length(); ++i) {
                pre = 26 * pre + chs[i] - 'a';
                res = pre + 1;
            }

            for (int i = s.length(); i < len; ++i) {
                pre = 26 * pre;
                res = pre;
            }
        } else {
            for (int i = 0; i < len; ++i) {
                pre = 26 * pre + chs[i] - 'a';
                res = pre + 1;
            }
        }

        return res;
    }
           

其中最关键的是pos函数，它采用的思想是用一个pre变量表示在字符串s的当前字符可自由变化的前缀个数，当位置不超过字符串长度的时候，pre=26*pre+chs[i]-'a'，结果变量res=pre+1，因为要加上字符本身。如果位置超过了字符串长度，pre=26*pre，res=pre。

答题思路来自于左程云老师，非常感谢！