Daily Archives: August 4, 2016

leetcode 91.

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

The number of ways decoding "12" is 2.

Solution. This is another dp problem. If we want to compute str[X1, X2, …, Xi-2, Xi-1, Xi].

1. Check if Xi is a valid one letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2, Xi-1]

2. Check if Xi-1Xi is a valid two letter number.
If it is, str[X1, X2, …, Xi-2, Xi-1, Xi] += str[X1, X2, …, Xi-2]

public static int numDecodings(String s) {
    if (s.length() == 0 || s.charAt(0) == '0') {
        return 0;
    }
    int[] dp = new int[s.length() + 1];
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 1; i < s.length(); i++) {
        int oneLetterNum = Integer.parseInt(s.substring(i, i + 1));
        if (oneLetterNum > 0) {
            dp[i + 1] += dp[i];
        }
        int twoLetterNum = Integer.parseInt(s.substring(i - 1, i + 1));
        if (twoLetterNum >= 10 && twoLetterNum <= 26) {
            dp[i + 1] += dp[i - 1];
        }
    }
    System.out.println(Arrays.toString(dp));
    return dp[s.length()];
}

Check my code on github.

leetcode 92.

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Solution. Should return head if head is null or head only has 1 element.

We use a dummyHead pointing to head. Then we put start to the m – 1 position, put pre to m position, put curr to m + 1 position. Each time, we move curr after start. At the beginning, start points to dummyHead.  Process for reversing [2..4] is like below.

If there are only 2 elements, the initial is like this:

public static ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;
    ListNode start = dummyHead;
    for (int i = 1; i < m; i++) {
        start = start.next;
    }
    ListNode pre = start.next, curr = start.next.next;
    for (int i = 1; i <= n - m; i++) {
        pre.next = curr.next;
        curr.next = start.next;
        start.next = curr;
        curr = pre.next;
    }
    return dummyHead.next;
}

Check my code on github.