一道字符串填充算法题

偶然在idailylife的博客上看到Indeed Tokyo 笔试题一道,觉得很有趣,就思考了下这题,这里记录一下。

问题描述

输入字符串str=a[0] a[1] ... a[N],其中0<N<=10^5。字符串的每一位是0-9?,需要用0-9填充各个问号的值,使得整个字符串成为一个数(允许前导0),并且满足任意连续10位上的字符(或理解成数字)a[i] a[i+1] ... a[i+9]不重复,输出解的个数。

例如,输入"04??2?7",输出应当为120.

分治法算法复杂度

分治法是一种常用的算法设计技巧,二分法就是其最常见的特例。所谓分治,分而治之也:

  • 分(divide):递归解决较小的问题
  • 治(conquer):从子问题的解构建原问题的解

一般来说,至少含有两个递归的程序才叫做分治法,只有一个递归的程序是不算的。下面来总结下分治法的算法复杂度问题,摘自《数据结构与算法分析——C语言描述》一书。