Leetcode Problem 1088. Confusing Number II

1088. Confusing Number II

Leetcode Solutions

DFS/Backtrack Approach for Confusing Numbers

  1. Convert the input number n to a string s.
  2. Define a recursive function dfs that takes the current prefix num, a boolean smaller indicating if num is guaranteed to be smaller than s, and the string s.
  3. If num has the same length as s, remove leading zeros and check if it is a confusing number after rotation. If it is, return 1, otherwise return 0.
  4. Initialize ans to 0 to accumulate the count of confusing numbers.
  5. Iterate over the digits '0', '1', '6', '8', and '9'. For each digit c:
    • If smaller is false and c is greater than the corresponding digit in s, break the loop.
    • Append c to num.
    • Recursively call dfs with the updated num and smaller.
    • Add the result of the recursive call to ans.
    • Backtrack by removing the last character from num.
  6. Return ans.
  7. Call dfs with an empty string num, smaller set to false, and the string s to start the process.
UML Thumbnail

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...