impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        use std::collections::HashMap;
        let mut map = HashMap::new();
        for (i, num) in nums.iter().enumerate() {
            let complement = target - num;
            if map.contains_key(&complement) {
                return vec![*map.get(&complement).unwrap() as i32, i as i32];
            }
            map.insert(num, i);
        }
        vec![]
    }
}

impl Solution {
    pub fn add_two_numbers(l1: Option<Box<ListNode>>, l2: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut ans = ListNode::new(-1);
        let (mut l1, mut l2) = (l1, l2);
        let mut remainder = 0;
        let mut p = &mut ans;
        while l1.is_some() || l2.is_some() || remainder != 0 {
            if let Some(a) = l1 {
                l1 = a.next;
                remainder += a.val;
            }
            if let Some(b) = l2 {
                l2 = b.next;
                remainder += b.val;
            }
            p.next = Some(Box::new(ListNode::new(remainder % 10)));
            p = p.next.as_mut().unwrap().as_mut();
            remainder /= 10;
        }
        ans.next
    }
}

impl Solution {
    pub fn length_of_longest_substring(s: String) -> i32 {
        use std::cmp::max;
        use std::collections::HashSet;
        let mut dict = HashSet::new();
        let s = s.as_bytes();
        let (mut ans, mut i) = (0, 0);
        for j in 0..s.len() {
            while dict.contains(&s[j]) {
                dict.remove(&s[i]);
                i += 1;
            }
            dict.insert(s[j]);
            ans = max(ans, (j - i + 1) as i32);
        }
        ans
    }
}

func longestPalindrome(s string) string {
	dp, n, ans := make([][]bool, len(s)), len(s), s[:1]
	for i := 0; i < n; i++ {
		dp[i] = make([]bool, n)
		dp[i][i] = true
	}
	for end := 1; end < n; end++ {
		for start := 0; start < end; start++ {
			if s[start] == s[end] && (end-start == 1 || dp[start+1][end-1]) {
				dp[start][end] = true
				if end-start+1 > len(ans) {
					ans = s[start : end+1]
				}
			}
		}
	}
	return ans
}

func palindrome(s string, i, j int) string {
	for i >= 0 && j < len(s) {
		if s[i] == s[j] {
			i, j = i-1, j+1
		} else {
			break
		}
	}
	return s[i+1 : j]
}

func longestPalindrome(s string) string {
	n, ans := len(s), s[:1]
	for i := 0; i < n; i++ {
		r1, r2 := palindrome(s, i, i), palindrome(s, i, i+1)
		if len(r1) > len(ans) {
			ans = r1
		}
		if len(r2) > len(ans) {
			ans = r2
		}
	}
	return ans
}

impl Solution {
    pub fn max_area(height: Vec<i32>) -> i32 {
        use std::cmp::{max, min};
        let mut max_area = 0;
        let (mut left, mut right) = (0, height.len() - 1);
        while left < right {
            let area = ((right - left) as i32) * min(height[left], height[right]);
            max_area = max(max_area, area);
            match height[left] < height[right] {
                true => left += 1,
                false => right -= 1,
            }
        }
        max_area
    }
}

func longestCommonPrefix(strs []string) string {
    for i := 0; i < len(strs[0]); i++ {
        for j := 1; j < len(strs); j++ {
            if len(strs[j]) < i+1 || strs[j][i] != strs[0][i] {
                return strs[0][:i]
            }
        }
    }
    return strs[0]
}

func threeSum(nums []int) [][]int {
	ans, n := make([][]int, 0), len(nums)
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		for i > 0 && i < n && nums[i] == nums[i-1] {
			i++
		}
		for j, k := i+1, n-1; j < k; {
			if nums[i]+nums[j]+nums[k] == 0 {
				ans = append(ans, []int{nums[i], nums[j], nums[k]})
				j, k = j+1, k-1
				for j < k && nums[j] == nums[j-1] {
					j++
				}
				for j < k && nums[k+1] == nums[k] {
					k--
				}
			} else if nums[i]+nums[j]+nums[k] > 0 {
				k--
			} else {
				j++
			}
		}
	}
	return ans
}

func threeSumClosest(nums []int, target int) int {
	sum, n := 1<<31-1, len(nums)
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		for left, right := i+1, n-1; left < right; {
			if nums[i]+nums[left]+nums[right] >= target {
				if nums[i]+nums[left]+nums[right]-target < abs(sum-target) {
					sum = nums[i] + nums[left] + nums[right]
				}
				right--
			} else {
				if target-(nums[i]+nums[left]+nums[right]) < abs(sum-target) {
					sum = nums[i] + nums[left] + nums[right]
				}
				left++
			}
		}
	}
	return sum
}

func abs(x int) int {
	if x < 0 {
		return -1 * x
	}
	return x
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	d := []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	var dfs func(digits string) []string

	dfs = func(digits string) []string {
		ans := []string{}
		if len(digits) == 0 {
			return []string{""}
		}
		subLetters := dfs(digits[1:])
		digit := int(digits[0] - '2')
		for i := 0; i < len(d[digit]); i++ {
			x := string(d[digit][i])
			for _, letter := range subLetters {
				ans = append(ans, x+letter)
			}
		}
		return ans
	}
	return dfs(digits)
}

func letterCombinations(digits string) []string {
	if len(digits) == 0 {
		return []string{}
	}
	ans, d := []string{""}, []string{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}

	for i := 0; i < len(digits); i++ {
		digit, t := d[digits[i]-'2'], []string{}
		for i := 0; i < len(digit); i++ {
			for _, v := range ans {
				t = append(t, v+string(digit[i]))
			}
		}
		ans = t
	}
	return ans
}

func fourSum(nums []int, target int) [][]int {
	ans, n := [][]int{}, len(nums)
	sort.Ints(nums)
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			for l, r := j+1, n-1; l < r; {
				if nums[i]+nums[j]+nums[l]+nums[r] == target {
					ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
					l, r = l+1, r-1
					for l < r && nums[l] == nums[l-1] {
						l++
					}
					for l < r && nums[r] == nums[r+1] {
						r--
					}
				} else if nums[i]+nums[j]+nums[l]+nums[r] < target {
					l++
				} else {
					r--
				}
			}
			for j+1 < n && nums[j+1] == nums[j] {
				j++
			}
		}
		for i+1 < n && nums[i+1] == nums[i] {
			i++
		}
	}
	return ans
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{Next: head}
	pre, now := dummy, dummy
	for ; n > 0; n-- {
		now = now.Next
	}

	for now.Next != nil {
		pre, now = pre.Next, now.Next
	}
	pre.Next = pre.Next.Next
	return dummy.Next
}

func isValid(s string) bool {
	stack, parent := []byte{}, map[byte]byte{')': '(', '}': '{', ']': '['}
	for i := 0; i < len(s); i++ {
		if s[i] == '(' || s[i] == '[' || s[i] == '{' {
			stack = append(stack, s[i])
		} else {
			if len(stack) > 0 && parent[s[i]] == stack[len(stack)-1] {
				stack = stack[:len(stack)-1]
			} else {
				return false
			}
		}
	}
	return len(stack) == 0
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for ; list1 != nil && list2 != nil; p = p.Next {
		if list1.Val < list2.Val {
			p.Next, list1 = list1, list1.Next
		} else {
			p.Next, list2 = list2, list2.Next
		}
	}
	if list1 != nil {
		p.Next = list1
	} else {
		p.Next = list2
	}
	return dummy.Next
}

func generateParenthesis(n int) []string {
	ans := []string{}
	var backtrack func(left, right int, seqence string)
	backtrack = func(left, right int, seqence string) {
		if left == 0 && right == 0 {
			ans = append(ans, seqence)
			return
		}
		if left > right || left < 0 || right < 0 {
			return
		}

		backtrack(left-1, right, seqence+"(")
		backtrack(left, right-1, seqence+")")
	}
	backtrack(n, n, "")
	return ans
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
	var merge func(left, right int) *ListNode
	merge = func(left, right int) *ListNode {
		if left > right {
			return nil
		}
		if left == right {
			return lists[left]
		}
		mid := (left + right) / 2
		l := merge(left, mid)
		r := merge(mid+1, right)
		return mergeTwoLists(l, r)
	}
	return merge(0, len(lists)-1)
}

func mergeTwoLists(l1, l2 *ListNode) *ListNode {
	dummy := &ListNode{}
	p := dummy
	for ; l1 != nil && l2 != nil; p = p.Next {
		if l1.Val < l2.Val {
			p.Next, l1 = l1, l1.Next
		} else {
			p.Next, l2 = l2, l2.Next
		}
	}
	if l1 != nil {
		p.Next = l1
	} else {
		p.Next = l2
	}
	return dummy.Next
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	res := swapPairs(head.Next.Next)
	p := head.Next
	p.Next, head.Next = head, res
	return p
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	start, end := head, head
	for i := 0; i < k; i++ {
		if end == nil {
			return head
		}
		end = end.Next
	}
	res := reverse(start, end)
	start.Next = reverseKGroup(end, k)
	return res
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
	var dummy *ListNode = &ListNode{}
	p, cur := dummy, head
	for cur != nil {
		start := cur
		for i := 0; i < k; i++ {
			if cur == nil {
				p.Next = start
				return dummy.Next
			}
			cur = cur.Next
		}
		p.Next, p = reverse(start, cur), start
	}
	return dummy.Next
}

func reverse(start, end *ListNode) *ListNode {
	var pre *ListNode = nil
	for start != end {
		tmp := start.Next
		start.Next, pre = pre, start
		start = tmp
	}
	return pre
}

func removeDuplicates(nums []int) int {
	first, last := 0, 0
	for ; last < len(nums); last++ {
		if nums[last] != nums[first] {
			nums[first+1], first = nums[last], first+1
		}
	}
	return first + 1
}

func removeElement(nums []int, val int) int {
	first, last := 0, 0
	for ; last < len(nums); last++ {
		if nums[last] != val {
			nums[first], first = nums[last], first+1
		}
	}
	return first
}

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	for i := 0; i <= n-m; i++ {
		if haystack[i:i+m] == needle {
			return i
		}
	}
	return -1
}

func strStr(haystack string, needle string) int {
	n, m := len(haystack), len(needle)
	sha, target, left, right, mod := 0, 0, 0, 0, 1<<31-1
	multi := 1
	for i := 0; i < m; i++ {
		target = (target*256%mod + int(needle[i])) % mod
	}
	for i := 1; i < m; i++ {
		multi = multi * 256 % mod
	}

	for ; right < n; right++ {
		sha = (sha*256%mod + int(haystack[right])) % mod
		if right-left+1 < m {
			continue
		}
		// 此时 left~right 的长度已经为 needle 的长度 m 了，只需要比对 sha 值与 target 是否一致即可
		// 为避免 hash 冲突，还需要确保 haystack[left:right+1] 与 needle 相同
		if sha == target && haystack[left:right+1] == needle {
			return left
		}
		// 未匹配成功，left 右移一位
		sha = (sha - (int(haystack[left])*multi)%mod + mod) % mod
		left++
	}
	return -1
}

func divide(a int, b int) int {
	sign, ans, INT32_MAX, INT32_MIN, LIMIT := false, 0, 1<<31-1, -1<<31, -1<<31/2
	if (a > 0 && b < 0) || (a < 0 && b > 0) {
		sign = true
	}
	a, b = convert(a), convert(b)
	for a <= b {
		cnt := 0
		// (b<<cnt) >= LIMIT 是为了避免 b<<(cnt+1) 发生溢出
		for (b<<cnt) >= LIMIT && a <= (b<<(cnt+1)) {
			cnt++
		}
		ans = ans + -1<<cnt
		a = a - b<<cnt
	}
	if sign {
		return ans
	}
	if ans == INT32_MIN {
		return INT32_MAX
	}
	return -ans
}

func convert(v int) int {
	if v > 0 {
		return -v
	}
	return v
}

func findSubstring(s string, words []string) []int {
	ans, exist, n, m, w := []int{}, map[string]int{}, len(s), len(words), len(words[0])
	for _, w := range words {
		exist[w]++
	}
	for i := 0; i < w; i++ {
		help := map[string]int{}
		for j, k := i, i+w-1; k < n; k += w {
			sub := s[k-w+1 : k+1]
			help[sub]++
			if k-j+1 < m*w {
				continue
			}
			cnt := 0
			for key := range exist {
				if exist[key] == help[key] {
					cnt++
				}
			}
			if cnt == len(exist) {
				ans = append(ans, j)
			}
			help[s[j:j+w]]--
			j += w
		}
	}
	return ans
}

func nextPermutation(nums []int) {
	l, r := len(nums)-2, len(nums)-1
	for l >= 0 && nums[l] >= nums[l+1] {
		l--
	}
	for l >= 0 && r > l && nums[r] <= nums[l] {
		r--
	}
	if l >= 0 && r >= 0 {
		nums[l], nums[r] = nums[r], nums[l]
	}
	for i, j := l+1, len(nums)-1; i < j; i, j = i+1, j-1 {
		nums[i], nums[j] = nums[j], nums[i]
	}
}

func longestValidParentheses(s string) int {
	dp, ans := make([]int, len(s)), 0
	if len(s) > 1 && s[0] == '(' && s[1] == ')' {
		ans, dp[1] = 2, 2
	}
	for i := 2; i < len(s); i++ {
		if s[i] == ')' && s[i-1] == '(' {
			dp[i] = dp[i-2] + 2
		} else if s[i] == ')' && i-dp[i-1]-1 >= 0 && s[i-dp[i-1]-1] == '(' {
			dp[i] = dp[i-1] + 2
			if i-dp[i-1]-2 >= 0 {
				dp[i] += dp[i-dp[i-1]-2]
			}
		}
		if ans < dp[i] {
			ans = dp[i]
		}
	}
	return ans
}

func search(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)/2
		if nums[mid] == target {
			return mid
		} else if nums[mid] >= nums[left] {
			if nums[left] <= target && nums[mid] > target {
				right = mid - 1
			} else {
				left = mid + 1
			}
		} else {
			if nums[mid] < target && nums[right] >= target {
				left = mid + 1
			} else {
				right = mid - 1
			}
		}
	}
	return -1
}

func searchRange(nums []int, target int) []int {
	return []int{leftBound(nums, target), rightBound(nums, target)}
}

func leftBound(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	if left < len(nums) && nums[left] == target {
		return left
	}
	return -1
}

func rightBound(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] <= target {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}
	if right >= 0 && nums[right] == target {
		return right
	}
	return -1
}

func searchInsert(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		mid := left + (right-left)>>1
		if nums[mid] >= target {
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	return left
}

func isValidSudoku(board [][]byte) bool {
	// row, col, sub 分别表示第i行、第j列、第k个 3x3 宫内是否包含数字 1～9 中的某些数字
	row, col, sub := [9][9]bool{}, [9][9]bool{}, [9][9]bool{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			number := int(board[i][j] - byte('1'))
			if number < 0 || number >= 9 {
				continue
			}
			k := i/3*3 + j/3
			if row[i][number] || col[j][number] || sub[k][number] {
				return false
			}
			row[i][number], col[j][number], sub[k][number] = true, true, true
		}
	}
	return true
}

func solveSudoku(board [][]byte) {
	row, col, box, t := [9][9]bool{}, [9][9]bool{}, [9][9]bool{}, [][2]int{}
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			elem, k := int(board[i][j]-'1'), i/3*3+j/3
			if board[i][j] != '.' {
				row[i][elem], col[j][elem], box[k][elem] = true, true, true
			} else {
				t = append(t, [2]int{i, j})
			}
		}
	}
	var backtrack func(x int) bool

	backtrack = func(x int) bool {
		if x == len(t) {
			return true
		}
		i, j := t[x][0], t[x][1]
		for v := 1; v <= 9; v++ {
			if !row[i][v-1] && !col[j][v-1] && !box[i/3*3+j/3][v-1] {
				board[i][j] = byte('0' + v)
				row[i][v-1], col[j][v-1], box[i/3*3+j/3][v-1] = true, true, true
				if backtrack(x + 1) {
					return true
				}
				row[i][v-1], col[j][v-1], box[i/3*3+j/3][v-1] = false, false, false
			}
		}
		return false
	}
	backtrack(0)
}

func main() {
	v := [][]byte{
		{'5', '3', '.', '.', '7', '.', '.', '.', '.'},
		{'6', '.', '.', '1', '9', '5', '.', '.', '.'},
		{'.', '9', '8', '.', '.', '.', '.', '6', '.'},
		{'8', '.', '.', '.', '6', '.', '.', '.', '3'},
		{'4', '.', '.', '8', '.', '3', '.', '.', '1'},
		{'7', '.', '.', '.', '2', '.', '.', '.', '6'},
		{'.', '6', '.', '.', '.', '.', '2', '8', '.'},
		{'.', '.', '.', '4', '1', '9', '.', '.', '5'},
		{'.', '.', '.', '.', '8', '.', '.', '7', '9'},
	}
	solveSudoku(v)
	for i := 0; i < 9; i++ {
		for j := 0; j < 9; j++ {
			fmt.Printf("%c ", v[i][j])
		}
		fmt.Println()
	}
}

func countAndSay(n int) string {
	ans := "1"
	for i := 0; i < n-1; i++ {
		t := ""
		for l, r := 0, 0; r < len(ans); {
			for r < len(ans) && ans[l] == ans[r] {
				r++
			}
			t += fmt.Sprintf("%d%c", r-l, ans[l])
			l = r
		}
		ans = t
	}
	return ans
}

func combinationSum(candidates []int, target int) [][]int {
	ans, n := [][]int{}, len(candidates)
	var backtrack func(start, now int, data []int)
	backtrack = func(start, now int, data []int) {
		if now == target {
			ans = append(ans, append([]int{}, data...))
			return
		} else if now > target || start >= n {
			return
		}
		for i := start; i < n; i++ {
			data = append(data, candidates[i])
			backtrack(i, now+candidates[i], data)
			data = data[:len(data)-1]
		}
	}
	backtrack(0, 0, []int{})
	return ans
}

func combinationSum2(candidates []int, target int) [][]int {
	sort.Ints(candidates)
	ans := [][]int{}
	var backtrack func(start, sum int, data []int)
	backtrack = func(start, sum int, data []int) {
		// base case
		if sum == target {
			ans = append(ans, append([]int{}, data...))
			return
		} else if start == len(candidates) || sum > target {
			return
		}

		for i := start; i < len(candidates); i++ {
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			data = append(data, candidates[i])
			backtrack(i+1, sum+candidates[i], data)
			data = data[:len(data)-1]
		}
	}
	backtrack(0, 0, []int{})
	return ans
}

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		for nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i]-1] {
			nums[i], nums[nums[i]-1] = nums[nums[i]-1], nums[i]
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] != i+1 {
			return i + 1
		}
	}
	return n + 1
}

func firstMissingPositive(nums []int) int {
	n := len(nums)
	for i := 0; i < n; i++ {
		if nums[i] <= 0 {
			nums[i] = n + 1
		}
	}
	for i := 0; i < n; i++ {
		v := abs(nums[i])
		if v <= n {
			nums[v-1] = -abs(nums[v-1])
		}
	}
	for i := 0; i < n; i++ {
		if nums[i] > 0 {
			return i + 1
		}
	}
	return n + 1
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func trap(height []int) int {
	ans, lmax, rmax := 0, height[0], height[len(height)-1]
	for i, j := 0, len(height)-1; i <= j; {
		if lmax < height[i] {
			lmax = height[i]
		}
		if rmax < height[j] {
			rmax = height[j]
		}
		if lmax > rmax {
			ans += rmax - height[j]
			j--
		} else {
			ans += lmax - height[i]
			i++
		}
	}
	return ans
}

func multiply(num1, num2 string) string {
	if num1 == "0" || num2 == "0" {
		return "0"
	}
	ans := ""
	for i := 0; i < len(num2); i++ {
		tmp, a, mod := "", int(num2[i]-'0'), 0
		for j := len(num1) - 1; j >= 0; j-- {
			b := int(num1[j] - '0')
			tmp = fmt.Sprintf("%d", (a*b+mod)%10) + tmp
			mod = (a*b + mod) / 10
		}
		if mod != 0 {
			tmp = fmt.Sprintf("%d", mod) + tmp
		}
		ans = add(ans+"0", tmp)
	}
	return ans
}

func add(num1, num2 string) string {
	ans, mod := "", 0
	for len(num1) > 0 || len(num2) > 0 || mod > 0 {
		a, b := 0, 0
		if len(num1) > 0 {
			a, num1 = int(num1[len(num1)-1]-'0'), num1[:len(num1)-1]
		}
		if len(num2) > 0 {
			b, num2 = int(num2[len(num2)-1]-'0'), num2[:len(num2)-1]
		}
		ans = fmt.Sprintf("%d", (a+b+mod)%10) + ans
		mod = (a + b + mod) / 10
	}
	return ans
}

func isMatch(s string, p string) bool {
	// 1表示匹配， 2表示不匹配
	memo, m, n := make([][]int, len(s)+10), len(s), len(p)
	for i := 0; i < m+10; i++ {
		memo[i] = make([]int, n+10)
	}
	var backtrack func(p1, p2 int) bool

	backtrack = func(p1, p2 int) bool {
		if memo[p1][p2] != 0 {
			return memo[p1][p2] == 1
		}
		if p2 >= n {
			if p1 >= m {
				memo[p1][p2] = 1
			} else {
				memo[p1][p2] = 2
			}
			return memo[p1][p2] == 1
		}
		ans := false
		if p1 <= m && p[p2] == '*' {
			ans = backtrack(p1, p2+1) || backtrack(p1+1, p2)
		}

		if p1 < m && p[p2] == '?' {
			ans = backtrack(p1+1, p2+1)
		} else if p1 < m && s[p1] == p[p2] {
			ans = backtrack(p1+1, p2+1)
		}
		memo[p1][p2] = 2
		if ans {
			memo[p1][p2] = 1
		}
		return ans
	}
	return backtrack(0, 0)
}

func isMatch(s string, p string) bool {
	dp, m, n := make([][]bool, 0), len(s), len(p)
	for i := 0; i <= m; i++ {
		dp = append(dp, make([]bool, n+1))
	}
	dp[0][0] = true
	for i := 1; i <= n; i++ {
		if p[i-1] == '*' {
			dp[0][i] = true
		} else {
			break
		}
	}
	for i := 1; i <= m; i++ {
		for j := 1; j <= n; j++ {
			if s[i-1] == p[j-1] || p[j-1] == '?' {
				dp[i][j] = dp[i-1][j-1]
			} else if p[j-1] == '*' {
				dp[i][j] = dp[i][j-1] || dp[i-1][j]
			}
		}
	}
	return dp[m][n]
}

func jump(nums []int) int {
	dp, n := make([]int, len(nums)), len(nums)
	for i := 1; i < n; i++ {
		dp[i] = 10000
		for j := 0; j < i; j++ {
			if i-j <= nums[j] {
				if dp[i] > dp[j]+1 {
					dp[i] = dp[j] + 1
				}
			}
		}
	}
	return dp[n-1]
}

func jump(nums []int) int {
	maxDistence, step, end := 0, 0, 0
	for i := 0; i < len(nums)-1; i++ {
		if i+nums[i] > maxDistence {
			maxDistence = i + nums[i]
		}
		if i == end {
			step, end = step+1, maxDistence
		}
	}
	return step
}

func permute(nums []int) [][]int {
	ans, used, n := make([][]int, 0), make([]bool, len(nums)), len(nums)
	var backtrack func(vals []int)
	backtrack = func(vals []int) {
		if len(vals) == n {
			ans = append(ans, append([]int{}, vals...))
			return
		}
		for i := 0; i < n; i++ {
			if used[i] {
				continue
			}
			vals, used[i] = append(vals, nums[i]), true
			backtrack(vals)
			vals, used[i] = vals[:len(vals)-1], false
		}
	}
	backtrack([]int{})
	return ans
}

func permuteUnique(nums []int) [][]int {
	ans, n := [][]int{}, len(nums)
	sort.Ints(nums)
	var backtrack func(vals []int, used []bool)

	backtrack = func(vals []int, used []bool) {
		if len(vals) == n {
			ans = append(ans, append([]int{}, vals...))
			return
		}

		i := 0
		for ; i < n; i++ {
			if !used[i] {
				break
			}
		}
		for start := i; i < n; i++ {
			if used[i] || (i != start && nums[i] == nums[start]) {
				continue
			}
			start = i
			vals, used[i] = append(vals, nums[i]), true
			backtrack(vals, used)
			vals, used[i] = vals[:len(vals)-1], false
		}
	}
	backtrack([]int{}, make([]bool, n))
	return ans
}

func rotate(matrix [][]int) {
	n := len(matrix)
	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
		}
	}
	for i := 0; i < n; i++ {
		for j, k := 0, n-1; j < k; j, k = j+1, k-1 {
			matrix[i][j], matrix[i][k] = matrix[i][k], matrix[i][j]
		}
	}
}

func groupAnagrams(strs []string) [][]string {
	ans, used, n := [][]string{}, make([]bool, len(strs)), len(strs)
	for i := 0; i < n; i++ {
		if used[i] {
			continue
		}
		tmp := []string{strs[i]}
		used[i] = true
		for j := i + 1; j < n; j++ {
			if isAnagrams(strs[j], strs[i]) {
				tmp, used[j] = append(tmp, strs[j]), true
			}
		}
		ans = append(ans, tmp)
	}
	return ans
}

func isAnagrams(now, target string) bool {
	if len(now) != len(target) {
		return false
	}
	nc, tc := [26]int{}, [26]int{}
	for i := 0; i < len(now); i++ {
		nc[int(now[i]-'a')] += 1
		tc[int(target[i]-'a')] += 1
	}
	for i := 0; i < 26; i++ {
		if nc[i] != tc[i] {
			return false
		}
	}
	return true
}