Strings

Question 1

word break

Answer 1

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        return wordBreakMemo(s, new HashSet<>(wordDict), 0, new Boolean[s.length()]);
    }

private boolean wordBreakMemo(String s, Set wordDict, int start, Boolean[] memo) {
    if (start == s.length()) {
        return true;
    }
    if (memo[start] != null) {
        return memo[start];
    }
    for (int end = start + 1; end <= s.length(); end++) {
        if (wordDict.contains(s.substring(start, end)) && wordBreakMemo(s, wordDict, end, memo)) {
            return memo[start] = true;
        }
    }
    return memo[start] = false;
} }

public class Solution {
    public boolean wordBreak(String s, List wordDict) {
        Set wordDictSet = new HashSet<>(wordDict);
        boolean[] dp = new boolean[s.length() + 1];
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDictSet.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}

O(n^3)

Question 2

Add strings

Answer 2

class Solution {
    public String addStrings(String num1, String num2) {
        StringBuilder res = new StringBuilder();

    int carry = 0;
    int p1 = num1.length() - 1;
    int p2 = num2.length() - 1;
    while (p1 >= 0 || p2 >= 0) {
        int x1 = p1 >= 0 ? num1.charAt(p1) - '0' : 0;
        int x2 = p2 >= 0 ? num2.charAt(p2) - '0' : 0;
        int value = (x1 + x2 + carry) % 10;
        carry = (x1 + x2 + carry) / 10;
        res.append(value);
        p1--;
        p2--;    
    }

    if (carry != 0)
        res.append(carry);

    return res.reverse().toString();
} }