Solution 1

It is sufficient to try all candidates of \(S\) by trying each of a to z for each ? in \(T\), and check if \(S\) contains \(U\) as a (contiguous) substring.

There are \(26^4=456976\) candidates for \(S\), which can be enumerated efficiently with a quadruple for loop.

One can also check if \(S\) contains \(U\) as a substring with a double for loop. There are \((|S| - |U| + 1)\) candidates of positions in \(S\) where \(U\) occurs as a substring. Enumerate all such positions and check if the corresponding pairs of characters are the same.

Some languages may come with a standard feature that determines if it contains a specific substring. In C++, one can use the find function; in Python, one can use the in operator.

Sample code (C++)

Sample code (Python)

Solution 2

One can solve it without guessing actual \(S\) and only with a double for loop.

We enumerate all the \((|S| - |U| + 1)\) candidates of positions in \(S\) where \(U\) occurs as a substring, checking if the \(i\)-th through \((i+|U|-1)\)-th characters of \(S\) may match \(U\). The match criteria is:

• \(T_{i+j} =\) ? or \(T_{i+j} = U_j\) for all \(j=1,2,\dots,|U|\).

If this condition is satisfied, one can make \(S_{i+j}=U_j\) by replacing \(T_{i+j}=\) ? with \(U_j\), so it can be matched as a substring. Thus, this condition is the necessity condition.

Also, if \(T_{i+j} \neq\) ? and \(T_{i+j} \neq U_j\) for some \(j\), then we always have \(S_{i+j} \neq U_j\), so it never match as a substring. Thus, this condition is the sufficient condition.

Sample code (C++)

Sample code (Python)