Day 34 of LeetCode

Documenting LeetCode solving.

Q99

14. Longest Common Prefix

Easy.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        int n = strs.length;
        int m = strs[0].length();

        for (int col = 0; col < m; col++) {
            for (int row = 1; row < n; row++) {
                String curr = strs[row], prev = strs[row - 1];
                if (col >= curr.length() || col >= prev.length() ||
                    curr.charAt(col) != prev.charAt(col)) {
                        return curr.substring(0, col);
                    }
            }
        }

        return strs[0];
    }
}

Q100

8. String to Integer (atoi)

Medium.

class Solution {
    public int myAtoi(String s) {
        s = s.trim();
        int n = s.length();
        int i = 0;
        int sign = 1;
        long res = 0;

        if (i == n) return 0;

        // Check - or +
        if (s.charAt(i) == '-') {
            sign = -1;
            i++;
        }
        else if (s.charAt(i) == '+') {
            i++;
        }
        if (i == n) return 0;

        // calculate integer
        while (i < n && s.charAt(i) >= '0' && s.charAt(i) <= '9') {
            res = res * 10 + (s.charAt(i) - '0');
            if (res > Integer.MAX_VALUE) {
                break;
            }
            i++;
        }

        // if overflow
        if ((int)res != res) {
            return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
        }

        return (int)res * sign;

    }
}

Q101

28. Find the Index of the First Occurrence in a String

Easy.

class Solution {
    public int strStr(String haystack, String needle) {
        int hayLen = haystack.length();
        int neeLen = needle.length();

        if (hayLen < neeLen) return -1;

        for (int i = 0; i <= hayLen - neeLen; i++) {
            int j = 0;
            while (j < neeLen && haystack.charAt(i + j) == needle.charAt(j)) {
                j++;
            }
            if (j == neeLen) return i;
        }

        return -1;
    }
}

Q102

151. Reverse Words in a String

Medium.

class Solution {
    public String reverseWords(String s) {
        s = s.trim();
        // split the string into string of array with separator as space 
        // or multiple spaces
        String[] arr = s.split("\\s+");

        int l = 0, r = arr.length - 1;
        while (l < r) {
            String temp = arr[l];
            arr[l] = arr[r];
            arr[r] = temp;
            l++;
            r--;
        }

        return String.join(" ", arr);
    }
}

No array extra space.

class Solution {
    public String reverseWords(String s) {
        // "  hello world  "
        s = s.trim(); // "hello world"
        s = reverse(s); // "dlrow olleh"

        StringBuilder sb = new StringBuilder();
        int l = 0, r = 0;
        while (r < s.length()) {
            while (r < s.length() && s.charAt(r) != ' ') {
                r++;
            }
            // Reverse each word: "dlrow" -> "world"
            sb.append(reverse(s.substring(l, r)));
            sb.append(' ');
            l = r;
            while (l < s.length() && s.charAt(l) == ' ') {
                l++;
            }
            r = l;
        }

        return sb.toString().trim();
    }

    public String reverse(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            sb.append(s.charAt(i));
        }

        return sb.toString();
    }
}

R20

2. Add Two Numbers

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode curr = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int val = carry;
            if (l1 != null) {
                val += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                val += l2.val;
                l2 = l2.next;
            }

            carry = val / 10;
            val = val % 10;
            curr.next = new ListNode(val);
            curr = curr.next;
        }

        return dummy.next;
    }
}