Given a number N. The task is to return all the numbers less than or equal to N in increasing order, with the fact that absolute difference between any adjacent digits of number should be 1.
 
Example 1:
Input: N = 20
Output: 10 12
Explanation: Diff between 1 and 0 and
Diff between 1 and 2 is one.
Example 2:
Input:
N = 9
Output: -1
Explanation: No such number exist.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function absDifOne() which takes an integer as input and returns a list of numbers.
 
Expected Time Complexity : O(2^{Number of Digits in N})
Expected Auxiliary Space : O(2^{Number of Digits in N})
Constraints:
1 <= N <= 10^{12}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Data structures

Mathematics

Starter code: #User function Template for python3

class Solution:
    def absDifOne(self, N):
        # code here

Solutions:
class Solution:

	def absDifOne(self, X):
		l = []
		for i in range(1, 10):

			def numbers(k):
				if k > X:
					return
				if k > 9:
					l.append(k)
				d = k % 10
				if d != 0:
					numbers(k * 10 + d - 1)
				if d != 9:
					numbers(k * 10 + d + 1)
			numbers(i)
		l.sort()
		return l


class Solution:

	def absDifOne(self, N):
		ans = []
		for num in range(1, 10):
			queue = []
			queue.append(num)
			while queue:
				curr = queue[0]
				queue.pop(0)
				if curr > 9 and curr <= N:
					ans.append(curr)
				if curr > N:
					continue
				last = curr % 10
				num1 = curr * 10 + last - 1
				num2 = curr * 10 + last + 1
				if last == 0:
					queue.append(num2)
				elif last == 9:
					queue.append(num1)
				else:
					queue.append(num1)
					queue.append(num2)
		if not ans:
			return [-1]
		else:
			return sorted(ans)


class Solution:

	def absDifOne(self, N):
		ans = set()

		def findAns(n, curr, ans):
			if n == 0:
				if int(curr) <= N:
					ans.add(int(curr))
				return
			if int(curr) <= N and len(curr) > 1:
				ans.add(int(curr))
			if curr[-1] == '0':
				findAns(n - 1, curr + '1', ans)
			elif curr[-1] == '9':
				findAns(n - 1, curr + '8', ans)
			else:
				end = int(curr[-1])
				findAns(n - 1, curr + str(end - 1), ans)
				findAns(n - 1, curr + str(end + 1), ans)
		if N <= 10:
			return [-1]
		n = len(str(N))
		for i in range(1, 10):
			findAns(n - 1, str(i), ans)
		ans = list(ans)
		ans.sort()
		return ans


from collections import deque

class Solution:

	def absDifOne(self, N):
		q = deque()
		ans = []
		if N < 10:
			return [-1]
		for i in range(1, 10):
			q.append(i)
			while len(q) > 0:
				val = q.popleft()
				if val > 9:
					ans.append(val)
				lastDigit = val % 10
				left = val * 10 + lastDigit - 1
				right = val * 10 + lastDigit + 1
				if lastDigit == 0:
					if left <= N:
						q.append(right)
				elif lastDigit == 9:
					if right <= N:
						q.append(left)
				else:
					if left <= N:
						q.append(left)
					if right <= N:
						q.append(right)
		ans.sort()
		return ans


class Solution:

	def absDifOne(self, N):

		def growN(i, n, ans):
			if i > n:
				return ans
			if 9 < i <= n:
				ans.append(i)
			lastDigit = i % 10
			nextNum1 = i * 10 + lastDigit + 1
			nextNum_1 = i * 10 + lastDigit - 1
			if lastDigit == 0:
				growN(nextNum1, n, ans)
			elif lastDigit == 9:
				growN(nextNum_1, n, ans)
			else:
				growN(nextNum1, n, ans)
				growN(nextNum_1, n, ans)
			return ans
		ans = []
		for i in range(1, 10):
			ans.extend(growN(i, N, []))
		return sorted(ans)


class Solution:

	def absDifOne(self, N):
		return self.stepnum(0, N)

	def bfs(self, source, count, ans, k, visited, temp, d):
		if count >= k:
			ans.append(temp)
			return ans
		for j in d[source]:
			if visited[j] == False:
				self.bfs(j, count + 1, ans, k, visited, temp + str(j), d)
		return ans

	def stepnum(self, A, B):
		d = {0: [1], 9: [8]}
		for i in range(1, 9):
			d[i] = [i - 1, i + 1]
		n = len(str(A))
		m = len(str(B))
		final_ans = []
		for k in range(n, m + 1):
			for l in range(1, 10):
				temp = ''
				visited = [False] * 10
				ans = []
				ans = self.bfs(l, 1, ans, k, visited, temp + str(l), d)
				for i in ans:
					if int(i) >= A and int(i) <= B and (len(str(i)) > 1):
						final_ans.append(i)
		return final_ans


class Solution:

	def absDifOne(self, N):
		n = len(str(N))

		def recur(temp, length, n, ans):
			ans += [temp]
			if length == n:
				return
			else:
				last = int(temp[-1])
				if last == 0:
					recur(temp + str(1), length + 1, n, ans)
				elif last == 9:
					recur(temp + str(8), length + 1, n, ans)
				else:
					recur(temp + str(last + 1), length + 1, n, ans)
					recur(temp + str(last - 1), length + 1, n, ans)
		ans = []
		for i in range(1, 10):
			recur(str(i), 1, n, ans)
		res = []
		for i in range(len(ans)):
			ans[i] = int(ans[i])
			if ans[i] >= 10 and ans[i] <= N:
				res += [ans[i]]
		res.sort()
		return res


class Solution:

	def absDifOne(self, N):
		st = []
		ls = len(str(N))

		def f(i, s):
			if i >= 2:
				if int(s) <= N:
					st.append(s)
			if i == ls:
				return
			if s[-1] != '9':
				f(i + 1, s + str(int(s[-1]) + 1))
			if s[-1] != '0':
				f(i + 1, s + str(int(s[-1]) - 1))
		for i in range(1, 10):
			f(1, str(i))
		st.sort(key=lambda i: int(i))
		return st


class Solution:

	def absDifOne(self, N):
		ans = list()

		def solve(n, currentDigit, ans):
			if n == 0:
				if int(currentDigit) <= N:
					ans.append(int(currentDigit))
				return
			if int(currentDigit) <= N and len(currentDigit) > 1:
				ans.append(int(currentDigit))
			if currentDigit[-1] == '0':
				solve(n - 1, currentDigit + '1', ans)
			elif currentDigit[-1] == '9':
				solve(n - 1, currentDigit + '8', ans)
			else:
				end = int(currentDigit[-1])
				solve(n - 1, currentDigit + str(end - 1), ans)
				solve(n - 1, currentDigit + str(end + 1), ans)
		if N <= 10:
			return [-1]
		n = len(str(N))
		for i in range(1, 10):
			solve(n - 1, str(i), ans)
		ans.sort()
		return ans


class Solution:

	def absDifOne(self, N):
		num_digits = 0
		n = N
		while n > 0:
			n = n // 10
			num_digits += 1
		prev_nums = [[i] for i in range(10)]
		final_list = []
		base = 10
		for pos in range(2, num_digits + 1):
			new_nums = [[] for i in range(10)]
			for digit in range(10):
				prev_digits = []
				if digit > 0:
					prev_digits.append(digit - 1)
				if digit < 9:
					prev_digits.append(digit + 1)
				for prev_d in prev_digits:
					for num in prev_nums[prev_d]:
						curr_num = digit * base + num
						if curr_num > N:
							return final_list
						if digit != 0:
							final_list.append(curr_num)
						new_nums[digit].append(curr_num)
			base *= 10
			prev_nums = new_nums
		return final_list


class Solution:

	def absDifOne(self, N):
		myList = []
		digit = 0
		if len(str(N)) == 1:
			return []
		elif len(str(N)) == 2:
			digit = N
		else:
			digit = 100
		for x in range(10, digit + 1):
			nums = str(x)
			isNum = True
			for i in range(0, len(nums) - 1):
				if abs(int(nums[i]) - int(nums[i + 1])) == 1:
					continue
				else:
					isNum = False
					break
			if isNum:
				myList.append(int(x))
		if len(str(N)) > 2:
			dataLength = len(str(N)) - 2
			for j in range(1, dataLength + 1):
				lists = (f for f in myList if len(str(f)) == j + 1)
				for r in list(lists):
					lastDigit = r % 10
					if lastDigit == 0:
						if int(str(r) + str(lastDigit + 1)) <= N:
							myList.append(int(str(r) + str(lastDigit + 1)))
						else:
							break
					elif lastDigit == 9:
						if int(str(r) + str(lastDigit - 1)) <= N:
							myList.append(int(str(r) + str(lastDigit - 1)))
						else:
							break
					else:
						if int(str(r) + str(lastDigit - 1)) <= N:
							myList.append(int(str(r) + str(lastDigit - 1)))
						else:
							break
						if int(str(r) + str(lastDigit + 1)) <= N:
							myList.append(int(str(r) + str(lastDigit + 1)))
						else:
							break
		return myList