LeetCode 241 - Different Ways to Add Parentheses

Given a string of numbers and operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +,- and *.

Example 1

Input: "2-1-1".

((2-1)-1) = 0
(2-(1-1)) = 2

Output: [0, 2]

Example 2

Input: "2*3-4*5"

(2*(3-(4*5))) = -34
((2*3)-(4*5)) = -14
((2*(3-4))*5) = -10
(2*((3-4)*5)) = -10
(((2*3)-4)*5) = 10

Output: [-34, -14, -10, -10, 10]

https://leetcode.com/problems/different-ways-to-add-parentheses/

Solution:

1. public List<Integer> diffWaysToCompute(String s) {  
2.     String[] arr = s.split("[\\+\\-\\*\\/]");  
3.     String[] ops = s.split("\\d+"); // Note: the 1st item is a space  
4.     int n = arr.length;  
5.     int[] nums = new int[n];  
6.     for(int i=0; i<n; i++) {  
7.         nums[i] = Integer.parseInt(arr[i].trim());  
8.     }  
9.     return diffWays(nums, ops, 0, n-1);  
10. }  
11.   
12. public List<Integer> diffWays(int[] nums, String[] ops, int left, int right) {  
13.     List<Integer> list  = new ArrayList<>();  
14.     if(left == right) {  
15.         list.add(nums[left]);  
16.         return list;  
17.     }  
18.     for(int i=left+1; i<=right; i++) {  
19.         List<Integer> list1 = diffWays(nums, ops, left, i-1);  
20.         List<Integer> list2 = diffWays(nums, ops, i, right);  
21.         for(int num1:list1) {  
22.             for(int num2:list2) {  
23.                 switch(ops[i].charAt(0)) {  
24.                     case '+': list.add(num1+num2); break;  
25.                     case '-': list.add(num1-num2); break;  
26.                     case '*': list.add(num1*num2); break;  
27.                     case '/': list.add(num1/num2); break;  
28.                 }  
29.             }  
30.         }  
31.     }  
32.     return list;  
33. }  

From: http://yuanhsh.iteye.com/blog/2230557

LeetCode 68 - Text Justification

Given an array of words and a length L, format the text such that each line has exactly L characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly Lcharacters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line do not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left justified and no extra space is inserted between words.

For example,
words: ["This", "is", "an", "example", "of", "text", "justification."]
L: 16.

Return the formatted lines as:

[
   "This    is    an",
   "example  of text",
   "justification.  "
]

Note: Each word is guaranteed not to exceed L in length.

vector<string> fullJustify(vector<string>& words, int maxWidth) {
    vector<string> result;
    int i = 0, n = words.size();
    while(i < n) {
        int j(i), cnt(0), len(0);
        while(i<n && len+cnt+words[i].size()<=maxWidth) {
            len += words[i++].size();
            cnt++;
        }
        bool left = (cnt==1 || i==n); // should be left aligned or not
        int space = left ? 1 : (maxWidth-len) / (cnt-1);
        int rem   = left ? 0 : (maxWidth-len) % (cnt-1);
        string s;
        while(j < i) {
            s.append(words[j++]);
            if(j < i)
                s.append(space, ' ');
            if(rem > 0) {
                s.append(1, ' ');
                rem--;
            }
        }
        if(s.size() < maxWidth) {
            s.append(maxWidth-s.size(), ' ');
        }
        result.push_back(s);
    }
    return result;
}