Andrew has a combination lock.
The lock consists of multiple dials that are placed next to each other.
Each dial contains the digits 0 through 9, in order.
At any moment, exactly one of the digits on each dial is visible.
The string formed by the currently visible digits is called the current combination.
The visible digit on a dial can be changed by rotating the dial up or down.
Rotating the dial up changes 0 to 1, 1 to 2, and so on.
Note that the digits on a dial wrap around: if we rotate up a dial that shows a 9, it will show a 0 again.
Naturally, rotating the dial down changes the digit in the other direction.
We are able to rotate multiple dials at the same time, as long as they are next to each other.
More precisely, in a single turn we can take an arbitrarily long segment of *consecutive* dials, and rotate all of them *one step* in the same direction (i.e., either all of them up, or all of them down).
For example, suppose that the current combination is "123".
In one step, we can change it to many different combinations, including "012" (all three dials down), "234" (all three dials up), "133" (middle dial up), and "013" (first two dials down).
Note that we cannot change "123" to "224" in a single step.
You are given two String[]s: **P** and **Q**.
Concatenate the elements of **P** to get `S`.
`S` is the current combination.
Concatenate the elements of **Q** to get `T`.
`T` is the secret combination that unlocks the lock.
That is, to open the lock we need to change `S` into `T` by rotating some of the dials.
Return the smallest number of steps needed. |