Leetcode - Perform String Shifts
You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]:
-
directioncan be0(for left shift) or1(for right shift). -
amountis the amount by which stringsis to be shifted. -
A left shift by 1 means remove the first character of
sand append it to the end. -
Similarly, a right shift by 1 means remove the last character of
sand add it to the beginning.
Return the final string after all operations.
Example 1:
Input: s = "abc", shift = [[0,1],[1,2]] Output: "cab" Explanation: [0,1] means shift to left by 1. "abc" -> "bca" [1,2] means shift to right by 2. "bca" -> "cab"
1. Given a sum to track final shift count. When shifting left, sum - current. While shifting right, sum + current
2. If sum == 0, no need to shift. If sum > 0, shift right. If sum < 0, shift left.
3. This question is converted to rotate an array
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | func stringShift(s string, shift [][]int) string { if len(s) <= 1 { return s } sum := 0 for _, i := range shift { if i[0] == 0 { sum -= i[1] } else { sum += i[1] } } if sum == 0 { return s } if sum > 0 { // shift right if sum > len(s) { sum = sum % len(s) } str := []byte(s) shiftArr(str, sum) return string(str) } // shift left if 0-sum > len(s) { sum = sum % len(s) } str := []byte(s) shiftArr(str, len(s)+sum) return string(str)}func shiftArr(s []byte, k int) { reverse(s) reverse(s[:k]) reverse(s[k:])}func reverse(s []byte) { size := len(s) for i := 0; i < size/2; i++ { s[i], s[size-1-i] = s[size-1-i], s[i] }} |
评论 (0)
