A number is called a stepping number if all adjacent digits have an absolute difference of 1, e.g. '321' is a Stepping Number while 421 is not. Given two integers n and m, find the count of all the stepping numbers in the range [n, m].
Example 1:
Input: n = 0, m = 21
Output: 13
Explanation: Stepping no's are 0 1 2 3 4 5
6 7 8 9 10 12 21
Example 2:
Input: n = 10, m = 15
Output: 2
Explanation: Stepping no's are 10, 12
Your Task:  
You don't need to read input or print anything. Your task is to complete the function steppingNumbers() which takes the integer n and integer m as input parameters and returns the number of stepping numbers in the range between n and m.
Expected Time Complexity: O(log(M))
Expected Auxiliary Space: O(SN) where SN is the number of stepping numbers in the range
Constraints:
0 ≤ N < M ≤ 10^{7}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Graph traversal

Starter code: #User function Template for python3





class Solution:

    def steppingNumbers(self, n, m):

        # code here

        pass





Solutions:
class Solution:

	def steppingNumbers(self, n, m):

		def _solve(v):
			if v > m:
				return 0
			ans = 1 if n <= v <= m else 0
			last = v % 10
			if last > 0:
				ans += _solve(v * 10 + last - 1)
			if last < 9:
				ans += _solve(v * 10 + last + 1)
			return ans
		ans = 0 if n > 0 else 1
		for i in range(1, 10):
			ans += _solve(i)
		return ans


class Solution:

	def steppingNumbers(self, n, m):

		def dfs(k, ans):
			if k >= n and k <= m:
				ans += 1
			if k <= m:
				if str(k)[-1] != '0':
					num = int(str(k) + str(int(str(k)[-1]) - 1))
					ans = dfs(num, ans)
				if str(k)[-1] != '9':
					num = int(str(k) + str(int(str(k)[-1]) + 1))
					ans = dfs(num, ans)
			return ans
		ans = 0
		if 0 >= n and 0 <= m:
			ans += 1
		for i in range(1, 10):
			ans = dfs(i, ans)
		return ans
		pass


class Solution:

	def util(self, n, m, i, ans):
		if i > m:
			return
		if n <= i and i <= m:
			ans.append(i)
		last_digit = i % 10
		if last_digit != 0:
			self.util(n, m, i * 10 + (last_digit - 1), ans)
		if last_digit != 9:
			self.util(n, m, i * 10 + (last_digit + 1), ans)

	def steppingNumbers(self, n, m):
		ans = list()
		for i in range(1, 10):
			self.util(n, m, i, ans)
		ans = sorted(ans)
		return len(ans)


def dfs(n, m, stepNum):
	c = 0
	if stepNum <= m and stepNum >= n:
		c += 1
	if stepNum == 0 or stepNum > m:
		return c
	lastDigit = stepNum % 10
	stepNumA = stepNum * 10 + (lastDigit - 1)
	stepNumB = stepNum * 10 + (lastDigit + 1)
	if lastDigit == 0:
		c += dfs(n, m, stepNumB)
	elif lastDigit == 9:
		c += dfs(n, m, stepNumA)
	else:
		c += dfs(n, m, stepNumA) + dfs(n, m, stepNumB)
	return c

def displaySteppingNumbers(n, m):
	c = 0
	for i in range(10):
		c += dfs(n, m, i)
	return c

class Solution:

	def steppingNumbers(self, n, m):
		return displaySteppingNumbers(n, m)


class Solution:

	def steppingNumbers(self, n, m):
		global cnt

		def bfs(n, m, num):
			global cnt
			queue = []
			queue.append(num)
			while len(queue) > 0:
				num = queue.pop(0)
				if num <= m and num >= n:
					cnt += 1
				if num == 0 or num > m:
					continue
				lastDigit = num % 10
				neighbourA = num * 10 + (lastDigit - 1)
				neighbourB = num * 10 + (lastDigit + 1)
				if lastDigit == 0:
					queue.append(neighbourB)
				elif lastDigit == 9:
					queue.append(neighbourA)
				else:
					queue.append(neighbourA)
					queue.append(neighbourB)
		cnt = 0
		for i in range(10):
			bfs(n, m, i)
		return cnt


from collections import deque

class Solution:

	def steppingNumbers(self, n, m):
		d = deque()
		for i in range(1, 10):
			d.append(i)
		count = 0
		while len(d) != 0:
			temp = d.popleft()
			if temp >= n and temp <= m:
				count += 1
			remainder = temp % 10
			l_temp = temp * 10 + temp % 10 - 1
			r_temp = temp * 10 + temp % 10 + 1
			if l_temp <= m and remainder != 0:
				d.append(l_temp)
			if r_temp <= m and remainder != 9:
				d.append(r_temp)
		if n == 0:
			return count + 1
		return count


class Solution:

	def steppingNumbers(self, n, m):
		q = list(range(0, 10))
		ans = set()
		while q:
			x = q.pop()
			if x > m:
				continue
			if x >= n:
				ans.add(x)
			d = x % 10
			if d != 9:
				q.append(x * 10 + d + 1)
			if d != 0:
				q.append(x * 10 + d - 1)
		return len(ans)


class Solution:

	def steppingNumbers(self, n, m):
		ans = []
		for e in range(1, 10):
			queue = [e]
			while queue:
				front = queue.pop(0)
				if front <= m:
					if front >= n:
						ans.append(front)
					lastDigit = front % 10
					if lastDigit == 9:
						leftNo = front * 10 + 8
						queue.append(leftNo)
					elif lastDigit == 0:
						rightNo = front * 10 + 1
						queue.append(rightNo)
					else:
						leftNo = front * 10 + (lastDigit - 1)
						rightNo = front * 10 + (lastDigit + 1)
						queue.append(leftNo)
						queue.append(rightNo)
		count = len(ans)
		if n == 0:
			return count + 1
		else:
			return count


class Solution:

	def steppingNumbers(self, n, m):
		queue = list(range(1, 10))
		count = 0
		if n == 0:
			count += 1
		while queue:
			curr = queue.pop(0)
			if curr > m:
				continue
			if curr >= n:
				count += 1
			rem = curr % 10
			if rem != 0:
				queue.append(curr * 10 + rem - 1)
			if rem != 9:
				queue.append(curr * 10 + rem + 1)
		return count


from collections import deque

def bfs(n, m, num):
	cnt = 0
	q = deque()
	q.append(num)
	while q:
		stepNum = q.popleft()
		if stepNum >= n and stepNum <= m:
			cnt += 1
		if num == 0 or stepNum > m:
			continue
		lastDigit = stepNum % 10
		stepNumA = stepNum * 10 + (lastDigit - 1)
		stepNumB = stepNum * 10 + (lastDigit + 1)
		if lastDigit != 9:
			q.append(stepNumB)
		if lastDigit != 0:
			q.append(stepNumA)
	return cnt

class Solution:

	def steppingNumbers(self, n, m):
		ans = 0
		for i in range(10):
			ans += bfs(n, m, i)
		return ans


import sys

class Solution:

	def steppingNumbers(self, n, m):

		def helper(v):
			if v > m:
				return 0
			ans = 1 if n <= v <= m else 0
			last = v % 10
			if last > 0:
				ans += helper(v * 10 + last - 1)
			if last < 9:
				ans += helper(v * 10 + last + 1)
			return ans
		ans = 0 if n > 0 else 1
		for i in range(1, 10):
			ans += helper(i)
		return ans


from collections import defaultdict

class Solution:

	def __init__(self):
		self.res = 0

	def helper(self, num, low, high, adj_list):
		q = [num]
		while q:
			node = q.pop(0)
			if node >= low and node <= high:
				self.res += 1
			if node > high:
				continue
			x = node % 10
			for ele in adj_list[x]:
				val = node * 10 + ele
				q.append(val)
		return None

	def steppingNumbers(self, n, m):
		adj_list = defaultdict(list)
		for num in range(0, 9):
			adj_list[num].append(num + 1)
			adj_list[num + 1].append(num)
		for num in range(1, 10):
			node = num
			self.helper(node, n, m, adj_list)
		if n == 0:
			self.res += 1
		return self.res
		pass


import collections

class Solution:

	def steppingNumbers(self, n, m):
		processStack = [i for i in range(10)]
		result = set()
		while processStack:
			current = processStack.pop()
			if current > m:
				continue
			if n <= current:
				result.add(current)
			parentDigit = current % 10
			if parentDigit == 0:
				processStack.append(current * 10 + 1)
			elif parentDigit == 9:
				processStack.append(current * 10 + 8)
			else:
				processStack.append(current * 10 + (parentDigit - 1))
				processStack.append(current * 10 + (parentDigit + 1))
		return len(result)


from collections import deque

class Solution:

	def steppingNumbers(self, M, N):
		res = 1 if M == 0 else 0
		q = deque()
		for i in range(1, 10):
			q.append(i)
		while q:
			for _ in range(len(q)):
				x = q.popleft()
				if x > N:
					continue
				if M <= x <= N:
					res += 1
				dx = x % 10
				if dx == 0:
					q.append(x * 10 + 1)
				elif dx == 9:
					q.append(x * 10 + 8)
				else:
					(m, n) = (x * 10 + dx - 1, x * 10 + dx + 1)
					if m <= N:
						q.append(m)
					if n <= N:
						q.append(n)
		return res


class Solution:

	def steppingNumbers(self, M, N):
		self.res = 1 if M == 0 else 0

		def helper(x):
			if x > N:
				return
			if M <= x <= N:
				self.res += 1
			dx = x % 10
			if dx == 0:
				helper(x * 10 + dx + 1)
			elif dx == 9:
				helper(x * 10 + dx - 1)
			else:
				helper(x * 10 + dx + 1)
				helper(x * 10 + dx - 1)
		for i in range(1, 10):
			helper(i)
		return self.res


class Solution:

	def dfs(self, i, c, m, n):
		if i > m:
			return
		if i >= n:
			c[0] = c[0] + 1
		if i % 10 == 0:
			self.dfs(int(str(i) + '1'), c, m, n)
		elif i % 10 == 9:
			self.dfs(int(str(i) + '8'), c, m, n)
		else:
			self.dfs(int(str(i) + str(i % 10 - 1)), c, m, n)
			self.dfs(int(str(i) + str(i % 10 + 1)), c, m, n)

	def steppingNumbers(self, n, m):
		c = [0]
		for i in range(1, 10):
			self.dfs(i, c, m, n)
		if n == 0:
			c[0] = c[0] + 1
		return c[0]


class Solution:

	def steppingNumbers(self, n, m):
		count = 0

		def dfs(string, val):
			if int(string) > m:
				return 0
			res = 1
			if int(string) < n:
				res = 0
			if val < 9:
				res += dfs(string + str(val + 1), val + 1)
			if val >= 1:
				res += dfs(string + str(val - 1), val - 1)
			return res
		for i in range(1, 10):
			val = dfs(str(i), i)
			count += val
		if n == 0:
			count = count + 1
		return count


from queue import Queue

class Solution:

	def steppingNumbers(self, n, m):
		(q, ans) = (Queue(), 1 if n == 0 else 0)
		for i in range(10):
			if i > 0:
				q.put(str(i))
		while q.qsize() > 0:
			num = q.get()
			if int(num) >= n:
				ans += 1
			if num[-1] > '0':
				x = num + str(ord(num[-1]) - 49)
				if int(x) <= m:
					q.put(x)
			if num[-1] < '9':
				x = num + str(ord(num[-1]) - 47)
				if int(x) <= m:
					q.put(x)
		return ans


class Solution:

	def steppingNumbers(self, n, m):

		def dfs(num):
			if num > m:
				return 0
			temp = 0
			if n <= num <= m:
				temp += 1
			lastDigit = num % 10
			if lastDigit != 0:
				temp += dfs(num * 10 + lastDigit - 1)
			if lastDigit != 9:
				temp += dfs(num * 10 + lastDigit + 1)
			return temp
		ans = 0
		if n == 0:
			ans += 1
		for i in range(1, 10):
			ans += dfs(i)
		return ans


class Solution:

	def steppingNumbers(self, n, m):
		count = [0]
		if n == 0:
			count[0] += 1
		for i in range(1, 10):
			self.dfs(i, n, m, count)
		return count[0]

	def dfs(self, curr, n, m, count):
		if curr > m:
			return
		if curr >= n and curr <= m:
			count[0] += 1
		lastDigit = curr % 10
		if lastDigit == 9:
			self.dfs(curr * 10 + 8, n, m, count)
		elif lastDigit == 0:
			self.dfs(curr * 10 + 1, n, m, count)
		else:
			self.dfs(curr * 10 + (lastDigit + 1), n, m, count)
			self.dfs(curr * 10 + (lastDigit - 1), n, m, count)


class Solution:

	def steppingNumbers(self, n, m):
		temp = [1, 2, 3, 4, 5, 6, 7, 8, 9]
		count = 0
		while len(temp) > 0:
			node = temp.pop(0)
			r = node % 10
			if (r == 0 or r == 9) and node <= m:
				if r == 0:
					new_num = node * 10 + (r + 1)
				if r == 9:
					new_num = node * 10 + (r - 1)
				temp.append(new_num)
			elif r != 0 and node <= m:
				new_num1 = node * 10 + (r + 1)
				new_num2 = node * 10 + (r - 1)
				temp.append(new_num1)
				temp.append(new_num2)
			if node >= n and node <= m:
				count += 1
		if n <= 0:
			count += 1
		return count


class Solution:

	def steppingNumbers(self, n, m):

		def solve(val, n, m, ans):
			if val > m:
				return
			if val >= n and val <= m:
				ans.append(val)
			back = val % 10
			if back != 0:
				solve(val * 10 + (back - 1), n, m, ans)
			if back != 9:
				solve(val * 10 + (back + 1), n, m, ans)
		ans = []
		if n == 0:
			ans.append(0)
		for i in range(1, 10):
			solve(i, n, m, ans)
		ans.sort()
		return len(ans)
		pass


class Solution:

	def steppingNumbers(self, n, m):
		ans = 0
		for i in range(10):
			q = [i]
			while q:
				out = q.pop(0)
				if out >= n and out <= m:
					ans += 1
				if out > m or out == 0:
					continue
				ld = out % 10
				n1 = out * 10 + (ld + 1)
				n2 = out * 10 + (ld - 1)
				if ld == 0:
					q.append(n1)
				elif ld == 9:
					q.append(n2)
				else:
					q.append(n1)
					q.append(n2)
		if n == 0:
			ans += 1
		return ans


class Solution:

	def steppingNumbers(self, A, B):

		def solve(val, a, b, ans):
			if val > b:
				return
			if val >= a and val <= b:
				ans.append(val)
			back = val % 10
			if back != 0:
				solve(val * 10 + (back - 1), a, b, ans)
			if back != 9:
				solve(val * 10 + (back + 1), a, b, ans)
		ans = []
		if A == 0:
			ans.append(0)
		for i in range(1, 10):
			solve(i, A, B, ans)
		ans.sort()
		return len(ans)
		pass


class Solution:

	def steppingNumbers(self, n, m):
		res = 0
		for i in range(0, 10):
			q = []
			q.append(i)
			while len(q) > 0:
				num = q[0]
				q.pop(0)
				if num <= m and num >= n:
					res = res + 1
				if num < m and num > 0:
					last = num % 10
					if last == 9:
						q.append(num * 10 + last - 1)
					elif last == 0:
						q.append(num * 10 + last + 1)
					else:
						q.append(num * 10 + last + 1)
						q.append(num * 10 + last - 1)
		return res


class Solution:

	def func(self, temp_li, l):
		if l == 0:
			self.all.append(int(''.join([str(x) for x in temp_li])))
			return
		prev_num = temp_li[-1]
		if prev_num != 0:
			temp_li.append(prev_num - 1)
			self.func(temp_li, l - 1)
			temp_li.pop()
		if prev_num != 9:
			temp_li.append(prev_num + 1)
			self.func(temp_li, l - 1)
			temp_li.pop()
		return

	def steppingNumbers(self, n, m):
		self.all = []
		for i in range(len(str(n)), len(str(m)) + 1):
			for j in range(1, 10):
				temp_li = [j]
				self.func(temp_li, i - 1)
		if n == 0:
			self.all.append(0)
		self.all.sort()
		count = 0
		for x in self.all:
			if x >= n and x <= m:
				count += 1
		return count


class Solution:

	def steppingNumbers(self, n, m):

		def _solve(v):
			if v > m:
				return 0
			results = 1 if n <= v <= m else 0
			last = v % 10
			if last > 0:
				results += _solve(v * 10 + last - 1)
			if last < 9:
				results += _solve(v * 10 + last + 1)
			return results
		results = 0 if n > 0 else 1
		for x in range(1, 10):
			results += _solve(x)
		return results
		pass


class Solution:

	def steppingNumbers(self, n, m):
		q = list(range(10))
		seen = set(range(10))
		ans = 0
		while q:
			(x, *q) = q
			if n <= x <= m:
				ans += 1
			d = x % 10
			(incx, decx) = (x * 10 + d + 1, x * 10 + d - 1)
			if d != 9 and incx not in seen and (incx <= m):
				q.append(incx)
				seen.add(incx)
			if d != 0 and decx not in seen and (decx <= m):
				q.append(decx)
				seen.add(decx)
		return ans


class Solution:

	def steppingNumbers(self, n, m):

		def solve(m):
			count = 1
			if m < 0:
				return 0
			if m < 10:
				return m + 1
			queue = [1, 2, 3, 4, 5, 6, 7, 8, 9]
			while queue:
				t = queue.pop(0)
				count += 1
				rem = t % 10
				f = t * 10 + rem - 1
				s = t * 10 + rem + 1
				if rem == 0:
					if s <= m:
						queue.append(s)
				elif rem == 9:
					if f <= m:
						queue.append(f)
				else:
					if f <= m:
						queue.append(f)
					if s <= m:
						queue.append(s)
			return count
		return solve(m) - solve(n - 1)


class Solution:

	def steppingNumbers(self, n, m):
		ans = 0

		def sol(cur, n, m):
			nonlocal ans
			if n <= int(cur) <= m:
				ans += 1
			if int(cur) > m:
				return
			if int(cur[-1]) + 1 < 10:
				inc = cur + str(int(cur[-1]) + 1)
				sol(inc, n, m)
			if int(cur[-1]) - 1 > -1:
				inc = cur + str(int(cur[-1]) - 1)
				sol(inc, n, m)
		for i in range(1, 10):
			sol(str(i), n, m)
		if 0 >= n and 0 <= m:
			ans += 1
		return ans


class Solution:

	def steppingNumbers(self, n, m):
		ans = 0

		def traverse(number):
			nonlocal ans
			if number > m:
				return 0
			if number <= m and number >= n:
				ans += 1
			last = number % 10
			if last >= 1 and last < 9:
				traverse(number * 10 + (last - 1))
				traverse(number * 10 + (last + 1))
			elif last == 0:
				traverse(number * 10 + (last + 1))
			else:
				traverse(number * 10 + (last - 1))
		for i in range(1, 10):
			traverse(i)
		return ans if n > 0 else ans + 1


class Solution:

	def steppingNumbers(self, n, m):
		q = []
		for i in range(0, 10):
			q.append(i)
		c = 0
		while q:
			x = q.pop()
			if x >= n and x <= m:
				c = c + 1
			if x == 0 or x > m:
				continue
			ld = x % 10
			step1 = x * 10 + (ld - 1)
			step2 = x * 10 + (ld + 1)
			if ld == 0:
				q.append(step2)
			elif ld == 9:
				q.append(step1)
			else:
				q.append(step1)
				q.append(step2)
		return c


class Solution:

	def steppingNumbers(self, n, m):
		count = 0

		def do(k):
			nonlocal count
			if n <= k <= m:
				count += 1
			elif k > m:
				return
			rem = k
			rem %= 10
			if rem > 0:
				do(k * 10 + rem - 1)
			if rem < 9:
				do(k * 10 + rem + 1)
		for i in range(1, 10):
			do(i)
		return count + (1 if n == 0 else 0)


from collections import deque

def bfs(n, m, num):
	cnt = 0
	q = deque()
	q.append(num)
	while q:
		stepnum = q.popleft()
		if stepnum >= n and stepnum <= m:
			cnt += 1
		if num == 0 or stepnum > m:
			continue
		lastdigit = stepnum % 10
		stepnumA = stepnum * 10 + (lastdigit - 1)
		stepnumB = stepnum * 10 + (lastdigit + 1)
		if lastdigit != 9:
			q.append(stepnumB)
		if lastdigit != 0:
			q.append(stepnumA)
	return cnt

class Solution:

	def steppingNumbers(self, n, m):
		ans = 0
		for i in range(10):
			ans += bfs(n, m, i)
		return ans


class Solution:

	def steppingNumbers(self, n, m):

		def dfs(num):
			if num > m:
				return 0
			ans = 1 if n <= num <= m else 0
			last = num % 10
			if last > 0:
				ans += dfs(num * 10 + last - 1)
			if last < 9:
				ans += dfs(num * 10 + last + 1)
			return ans
		ans = 1 if n == 0 else 0
		for i in range(1, 10):
			ans += dfs(i)
		return ans


class Solution:

	def steppingNumbers(self, n, m):

		def dfs(x):
			ans = 0
			if x > m:
				return 0
			if x >= n and x <= m:
				ans += 1
			last = x % 10
			if last != 0:
				ans += dfs(x * 10 + (last - 1))
			if last != 9:
				ans += dfs(x * 10 + (last + 1))
			return ans
		ans = 0
		if n == 0:
			ans += 1
		for i in range(1, 10):
			ans += dfs(i)
		return ans
		pass


class Solution:

	def steppingNumbers(self, n, m):
		if n > m:
			return 'n must be less or equal to m'
		sn = [*range(10)]
		d = len(str(m))
		begin = 1
		end = 9
		if d == 1:
			return m - n + 1
		for i in range(2, d + 1):
			for k in range(begin, end + 1):
				x = str(sn[k])
				lastd = x[-1]
				if lastd == '0':
					y = x + '1'
					sn.append(int(y))
				elif lastd == '9':
					y = x + '8'
					sn.append(int(y))
				else:
					y = x + str(int(lastd) - 1)
					sn.append(int(y))
					y = x + str(int(lastd) + 1)
					sn.append(int(y))
			begin = end + 1
			end = len(sn) - 1
		count = sum((1 for i in sn if i >= n and i <= m))
		return count