Programming exercise: interweaved strings

I don’t quite remember where I saw this problem, but I’m sure it’s appeared in a number of places. Given two strings \(s\) and \(t\), determine whether a string \(u\) is formed by interweaving \(s\) and \(t\). That is, determine whether \(u\) can be formed by taking the first few characters of (say) \(s\), followed by the first few characters of \(t\), then the next few characters of \(s\), and so on. For example, the string “abccdcxey” can be formed by interweaving “abcde” with “ccxy”.

I took way too long thinking about how to set up the problem than I should have. In the end, I decided to quickly write up a solution that is easy to code, even if it may not be optimal. The solution uses an \((m+1) \times (n+1)\) table, with indices starting from \(0\), where the \((i,j)\) entry is a boolean value indicating whether it’s possible to form the \((i+j)\)-character prefix of \(u\) from the first \(i\) characters of \(s\) and the first \(j\) characters of \(t\).

Let \(m\) and \(n\) be the lengths of \(s\) and \(t\), respectively. Assume that \(u\) is of length \(m+n\). (This can be easily checked and handled at the beginning.) The function that determines whether \(u\) is formed by interweaving \(s\) and \(t\) is as follows:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

bool interweave(char *s, int m, char *t, int n, char *u) {
    bool **table = new_table(m+1, n+1);    
    table[0][0] = true;
 
    for( int row = 0; row < m+1; row++ ) {
        for( int col = 0; col < n+1; col++ ) {
            if( table[row][col] ) {
                if( row != m ) {
                    table[row+1][col] = (s[row] == u[row+col]);
                }
                if( col != n ) {
                    table[row][col+1] = (t[col] == u[row+col]);
                }
            }
        }
    }
 
    bool result = table[m][n];
    delete table;
    return result;
}

When programming on the whiteboard, it’s important not to get bogged down in details. In the above, I’ve assumed the existence of a function new_table(rows,cols) which returns a two-dimensional array of bools, of the requested number of rows and columns, with all entries initialised to false. This is simple enough to implement that I hope the interviewer won’t actually ask me to write it out during the interview, but in case I have to do so, here it is:

1
2
3
4
5
6
7
8
9
10

bool **new_table(int rows, int cols) {
    bool **table = new bool*[rows];
    for( int i = 0; i < rows; i++ ) {
        table[i] = new bool[cols];
        for( int j = 0; j < cols; j++ ) {
            table[i][j] = false;
        }
    }
    return table;
}

The algorithm runs in time \(O(m \times n)\) and also takes that much space. I wasn’t really satisfied with this solution because it doesn’t make use of the fact that the same prefix of \(u\) can be formed by interweaving prefixes of \(s\) and \(t\) in different ways. For example, “abcc” can be formed by interweaving “abc” and “c” in two different ways. Now, the above algorithm doesn’t perform redundant calculations, but only because we’re sweeping the table row-by-row in an orderly fashion.

One can, of course, contrive values for which most of the table actually needs to be visited, but for most values of \(s\) and \(t\), if one or more paths from the upper left corner to the lower right corner of the table exists, the only entries of the table that need to be visited are likely to be very close to these paths. It makes sense therefore to keep track of which entries in the table are actually necessary to visit.

The following code is closer to the algorithm I have in mind:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

bool interweave(char *s, int m, char *t, int n, char *u) {
    queue q = new queue(m+1,n+1);
    q.enqueue(0,0);
 
    bool result = false;
 
    while( !q.empty() ) {
        int row, col;
        q.dequeue(&row, &col);
 
        if( ( row == m ) && ( col == n ) ) {
            result = true;
            break;
        }
 
        if( ( row != m ) && ( s[row] == u[row+col] ) && !q.marked(row+1,col) ) {
            q.enqueue(row+1,col);
        }
        if( ( col != n ) && (t[col] == u[row+col] ) && !q.marked(row,col+1) ) {
            q.enqueue(row,col+1);
        }
    }
 
    delete queue;
    return result;
}

In the above, I’ve assumed the existence of a queue class that allows me to enqueue and dequeue pairs of integers consisting of a row and a column. A row-column pair is enqueued only if it corresponds to a prefix of \(u\) that can be formed by interweaving a prefix of \(s\) and a prefix of \(t\). Furthermore, the queue class also keeps track of whether a pair has ever been enqueued. The marked function returns true if that’s the case, and false otherwise. It can do this either using a two-dimensional array, as before, or it can use a fancier structure that trades off time for savings in space.

If a two-dimensional array is used, the algorithm will still require \(O(m \times n)\) time just to initialise it. However, the main loop in the interweave function will be \(O(m+n)\) for inputs for which there is little overlap or repetition in the input strings.

– davinci 11848