首页 > 代码库 > Interleaving String

Interleaving String

2024-07-26 16:28:21   218人阅读

这题首先要注意的是两个字符串，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


联系
我们