[Java/C++] Clean Code


  • 2

    DP Formula

    /**
     * dp[i][j] = a[i] == b[j] ? dp[i + 1][j + 1] :
     *            min(1 + dp[i + 1][j],  // delete a[i] + mindist between a.substr(i+1), b.substr(j)
     *                1 + dp[i][j + 1])  // delete b[j] + mindist between a.substr(i), b.substr(j+1)
     */
    

    Java

    class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length(), n = word2.length(), MAX = Integer.MAX_VALUE;
            char[] a = word1.toCharArray(), b = word2.toCharArray();
            int[][] dp = new int[m + 1][n + 1];
            for (int i = m; i >= 0; i--) {
                for (int j = n; j >= 0; j--) {
                    if (i < m || j < n)
                        dp[i][j] = i < m && j < n && a[i] == b[j] ?
                            dp[i + 1][j + 1] : 1 + Math.min((i < m ? dp[i + 1][j] : MAX), (j < n ? dp[i][j + 1] : MAX));
                }
            }
            return dp[0][0];
        }
    }
    

    C++

    class Solution {
    public:
        int minDistance(string a, string b) {
            int m = a.size(), n = b.size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
            for (int i = m; i >= 0; i--) {
                for (int j = n; j >= 0; j--) {
                    if (i < m || j < n)
                        dp[i][j] = i < m && j < n && a[i] == b[j] ?
                            dp[i + 1][j + 1] : 1 + min((i < m ? dp[i + 1][j] : INT_MAX), (j < n ? dp[i][j + 1] : INT_MAX));
                }
            }
            return dp[0][0];
        }
    };
    

  • 0

    WOW, I learn this function call

    template< class T >
    constexpr T min( std::initializer_list<T> ilist );
    

    from your code. Thanks


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.