A different implementation of 16.12(v1.4.8)

#1

In 16.12, book use a operator list to record multiply and addition. I used different method to let the multiply choice and multiplicand acting as arguments.

public class Solution
{
	/**
	 * 
	 * @param digits array of the digits.
	 * @param start starting point of current number.
	 * @param end ending point of current number.
	 * @param target target value.
	 * @param multiple true: the operator before the number is multiply, otherwise addition.
	 * @param multiplicand multiplicand of the multiply, only meaningful when {@link mulitple} is true.
	 * @return
	 */
	private String helper(final int[] digits, final int start, final int end, final int target, final boolean multiple, final int multiplicand)
	{
		// value of current number.
		int num = 0;
		int i;
		// Because all number is positive and only addition and multiply. a number can't be larger than the target value.
		for (i = start; i < end && num <= target; ++i)
		{
			num = num * 10 + digits[i];
			// previous operator is addition.
			if (!multiple)
			{
				// next operator is addition.
				final String post = helper(digits, i + 1, end, target - num, false, 0);
				if (null == post)
				{
					// Multiple.
					final String part = helper(digits, i + 1, end, target, true, num);
					if (null != part)
					{
						return String.valueOf(num) + "*" + part;
					}
				}
				else
				{
					return String.valueOf(num) + "+" + post;
				}
			}
			// previous operator is multiply
			else
			{
				// Make sure the product is less than or equal to target value.
				if (num * multiplicand <= target)
				{
					// Addition.
					final String post = helper(digits, i + 1, end, target - num * multiplicand, false, 0);
					if (null == post)
					{
						// Multiple.
						final String part = helper(digits, i + 1, end, target, true, num * multiplicand);
						if (null != part)
						{
							return String.valueOf(num) + "*" + part;
						}
					}
					else
					{
						return String.valueOf(num) + "+" + post;
					}
				}
			}
		}
		
		// Need to check when the remain part is a whole number.
		if (!multiple)
		{
			return (start != end && i == end && num == target) ? String.valueOf(target) : null;
		}
		else
		{
			// Product is equal to target value.
			return (start != end && i == end && num * multiplicand == target) ? String.valueOf(num) : null;
		}
	}
	
	public String ExpressionSynthesis(final int[] digits, final int k)
	{
		return helper(digits, 0, digits.length, k, false, 0);
	}
}
0 Likes
#2

Hey Peter,

Thanks for providing this alternative implementation, and it definitely looks good to me. One thing I am curious about is that why you want to pass the choices of operators in the function?

0 Likes
#3

Thank you very much for your interest.
As you see, if it’s addition, we can split this calculation as two parts. we already get the value (p1) of first part, so the result(p2) of remaining part should be (target - p1). Then we can use the recursion to solve the second part.
But for the multiply, it has higher priority so we can’t split it directly. Consider 23+1, we can only record the previous multiply result and keep going, if it is multiply again, we update the multiply result and move on such as 234+1, we can let it become 234+1=>64+1=>24+1, and finally we can get rid of all the multiply and meet the addition or the end, it’s same as the first condition.

0 Likes