algorithm - 猜猜给定随机三元组的字符串

Question

给定一个未知字符串，执行一个实用函数，称为

string returnRandomTripletFromString(string)

该函数从未知字符串中返回一个随机三元组，您还得到了字符串的长度

效用函数返回的随机三元组，将保持字符串中字母的相对顺序，

假设字符串是 helloworld 它会返回

'hel', 'wod', 'lor'

但它永远不会回来

'lhd'

因为h在字符串中l之前

你如何使用这个实用函数猜测字符串，使用最少的函数调用次数。

Answer 1

这可能发生在 多次 次调用随机三元组函数之后。

Suppose our string was "hello"

让调用随机三元组函数在每次调用时给出以下但不一定按此顺序:

ell
llo
hel
hlo
elo

如果我根据从随机三元组函数获得的字符创建一个图形:

从这个图中，我只能解释起始字母可能是

'H'

结尾字母可能是

'O'

Then if I find the longest path in the graph. I will get "hello" or "olleh" depending upon where I begin from.

此外，路径中访问的节点数将等于字符串的长度。

假设:

1. 我只能在调用随机三元组函数后创建此图 多次。
2. 每次我从随机函数中得到唯一的三元组来构建图