String Operations (Edit Distance, Word Break, String Decoding)

Edit Distance (LeetCode 72)

Find the minimum number of operations (insert, delete, or replace) required to convert word1 to word2.

DP Approach:

int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    
    // Boundary conditions: distance between empty string and word of length i/j
    for (int i = 0; i <= m; i++) dp[i][0] = i;
    for (int j = 0; j <= n; j++) dp[0][j] = j;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                // If characters are the same, no new operation is needed
                dp[i][j] = dp[i - 1][j - 1];  
            } else {
                // Take the minimum of replace, delete, or insert operations
                dp[i][j] = 1 + Math.min(dp[i - 1][j - 1],   // Replace
                               Math.min(dp[i - 1][j],       // Delete from word1
                                        dp[i][j - 1]));     // Insert into word1
            }
        }
    }
    return dp[m][n];
}

State Definition: dp[i][j] represents the minimum operations to convert word1[0..i-1] into word2[0..j-1].

Word Break (LeetCode 139)

Determine if a string can be segmented into a space-separated sequence of one or more dictionary words.

boolean wordBreak(String s, List<String> wordDict) {
    Set<String> dict = new HashSet<>(wordDict);
    int n = s.length();
    boolean[] dp = new boolean[n + 1];
    dp[0] = true;  // Empty string is breakable
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            // If prefix s[0..j-1] is breakable and s[j..i-1] is in dict
            if (dp[j] && dict.contains(s.substring(j, i))) {
                dp[i] = true;
                break;
            }
        }
    }
    return dp[n];
}

Optimization Tip: Tracking the maximum word length in the dictionary can help limit the inner loop range.

Decode String (LeetCode 394)

Decode strings like 3[a2[c]] into accaccacc using stacks to track counts and partial strings.

String decodeString(String s) {
    Deque<Integer> countStack = new ArrayDeque<>();
    Deque<StringBuilder> strStack = new ArrayDeque<>();
    StringBuilder currentStr = new StringBuilder();
    int k = 0;

    for (char c : s.toCharArray()) {
        if (Character.isDigit(c)) {
            k = k * 10 + (c - '0');
        } else if (c == '[') {
            countStack.push(k);
            strStack.push(currentStr);
            currentStr = new StringBuilder();
            k = 0;
        } else if (c == ']') {
            int repeatTimes = countStack.pop();
            StringBuilder decoded = strStack.pop();
            // Append current built string repeatTimes
            for (int i = 0; i < repeatTimes; i++) decoded.append(currentStr);
            currentStr = decoded;
        } else {
            currentStr.append(c);
        }
    }
    return currentStr.toString();
}

Reverse Words in a String (LeetCode 151)

String reverseWords(String s) {
    // Trim and split by any number of whitespaces
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
        sb.append(words[i]);
        if (i > 0) sb.append(' ');
    }
    return sb.toString();
}

Advanced (O(1) Space): Reverse the entire string first, then reverse each word within it to restore their order.

Longest Common Subsequence (LeetCode 1143)

Find the length of the longest subsequence shared by two strings (not necessarily contiguous).

int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}