首页 > 代码库 > Interleaving String

Interleaving String

这题首先要注意的是两个字符串,Interleave得到一个新的字符串,原来字符串中的字符的顺序是不会改变的。

试想,如果枚举s1和s2所能组成的所有字符串,那将是很恐怖的。因为两个字串中的顺序不变,如果能将之类比Minimum Path Sum中,一个m X n的网格,从左上角走到右下角的过程,事情就相当好办了。仔细想想,那里面是只能向左或向下,总的向左和向下的步数是一定的,只是这两种走法如何间隔的问题!几乎完全一样:

    int minPathSum(vector<vector<int> > &grid) {    if (grid.empty())        return 0;    int m = grid.size();    int n = grid[0].size();    int *cost = new int[m * n];    for (int i = 0; i < m * n; i++)        cost[i] = 0;    cost[0] = grid[0][0];    for (int j = 1; j < n; j++)        cost[0 * n + j] = cost[0 * n + j - 1] + grid[0][j];    for (int i = 1; i < m; i++)        cost[i * n + 0] = cost[(i - 1) * n + 0] + grid[i][0];    for (int i = 1; i < m; i++){        for (int j = 1; j < n; j++){            cost[i * n + j] = min(cost[(i - 1) * n + j], cost[i * n + j - 1]) + grid[i][j];        }    }    int result = cost[m * n - 1];    delete[] cost;    return result;    }

 

Interleaving String