Question

2375. 根据模式串构造最小数字

English Version

题目描述

给你下标从 0 开始、长度为 n 的字符串 pattern ，它包含两种字符，'I' 表示 上升 ，'D' 表示 下降 。

你需要构造一个下标从 0 开始长度为 n + 1 的字符串，且它要满足以下条件：

• num 包含数字 '1' 到 '9' ，其中每个数字 至多 使用一次。
• 如果 pattern[i] == 'I' ，那么 num[i] < num[i + 1] 。
• 如果 pattern[i] == 'D' ，那么 num[i] > num[i + 1] 。

请你返回满足上述条件字典序 最小 的字符串_ _num。

 

示例 1：

输入：pattern = "IIIDIDDD"
输出："123549876"
解释：
下标 0 ，1 ，2 和 4 处，我们需要使 num[i] < num[i+1] 。
下标 3 ，5 ，6 和 7 处，我们需要使 num[i] > num[i+1] 。
一些可能的 num 的值为 "245639871" ，"135749862" 和 "123849765" 。
"123549876" 是满足条件最小的数字。
注意，"123414321" 不是可行解因为数字 '1' 使用次数超过 1 次。

示例 2：

输入：pattern = "DDD"
输出："4321"
解释：
一些可能的 num 的值为 "9876" ，"7321" 和 "8742" 。
"4321" 是满足条件最小的数字。

 

提示：

• 1 <= pattern.length <= 8
• pattern 只包含字符 'I' 和 'D' 。

解法

方法一：DFS

定义 $dfs(u)$，其中 $u$ 表示当前答案字符串的长度。从 $u=0$ 开始搜索，直至找到第一个符合条件的字符串。

时间复杂度 $O(n!)$，空间复杂度 $O(n)$。其中 $n$ 表示字符串 $pattern$ 的长度。

class Solution:
  def smallestNumber(self, pattern: str) -> str:
    def dfs(u):
      nonlocal ans
      if ans:
        return
      if u == len(pattern) + 1:
        ans = ''.join(t)
        return
      for i in range(1, 10):
        if not vis[i]:
          if u and pattern[u - 1] == 'I' and int(t[-1]) >= i:
            continue
          if u and pattern[u - 1] == 'D' and int(t[-1]) <= i:
            continue
          vis[i] = True
          t.append(str(i))
          dfs(u + 1)
          vis[i] = False
          t.pop()

    vis = [False] * 10
    t = []
    ans = None
    dfs(0)
    return ans

class Solution {
  private boolean[] vis = new boolean[10];
  private StringBuilder t = new StringBuilder();
  private String p;
  private String ans;

  public String smallestNumber(String pattern) {
    p = pattern;
    dfs(0);
    return ans;
  }

  private void dfs(int u) {
    if (ans != null) {
      return;
    }
    if (u == p.length() + 1) {
      ans = t.toString();
      return;
    }
    for (int i = 1; i < 10; ++i) {
      if (!vis[i]) {
        if (u > 0 && p.charAt(u - 1) == 'I' && t.charAt(u - 1) - '0' >= i) {
          continue;
        }
        if (u > 0 && p.charAt(u - 1) == 'D' && t.charAt(u - 1) - '0' <= i) {
          continue;
        }
        vis[i] = true;
        t.append(i);
        dfs(u + 1);
        t.deleteCharAt(t.length() - 1);
        vis[i] = false;
      }
    }
  }
}

class Solution {
public:
  string ans = "";
  string pattern;
  vector<bool> vis;
  string t = "";

  string smallestNumber(string pattern) {
    this->pattern = pattern;
    vis.assign(10, false);
    dfs(0);
    return ans;
  }

  void dfs(int u) {
    if (ans != "") return;
    if (u == pattern.size() + 1) {
      ans = t;
      return;
    }
    for (int i = 1; i < 10; ++i) {
      if (!vis[i]) {
        if (u && pattern[u - 1] == 'I' && t.back() - '0' >= i) continue;
        if (u && pattern[u - 1] == 'D' && t.back() - '0' <= i) continue;
        vis[i] = true;
        t += to_string(i);
        dfs(u + 1);
        t.pop_back();
        vis[i] = false;
      }
    }
  }
};

func smallestNumber(pattern string) string {
  vis := make([]bool, 10)
  t := []byte{}
  ans := ""
  var dfs func(u int)
  dfs = func(u int) {
    if ans != "" {
      return
    }
    if u == len(pattern)+1 {
      ans = string(t)
      return
    }
    for i := 1; i < 10; i++ {
      if !vis[i] {
        if u > 0 && pattern[u-1] == 'I' && int(t[len(t)-1]-'0') >= i {
          continue
        }
        if u > 0 && pattern[u-1] == 'D' && int(t[len(t)-1]-'0') <= i {
          continue
        }
        vis[i] = true
        t = append(t, byte('0'+i))
        dfs(u + 1)
        vis[i] = false
        t = t[:len(t)-1]
      }
    }
  }
  dfs(0)
  return ans
}

function smallestNumber(pattern: string): string {
  const n = pattern.length;
  const res = new Array(n + 1).fill('');
  const vis = new Array(n + 1).fill(false);
  const dfs = (i: number, num: number) => {
    if (i === n) {
      return;
    }

    if (vis[num]) {
      vis[num] = false;
      if (pattern[i] === 'I') {
        dfs(i - 1, num - 1);
      } else {
        dfs(i - 1, num + 1);
      }
      return;
    }

    vis[num] = true;
    res[i] = num;

    if (pattern[i] === 'I') {
      for (let j = res[i] + 1; j <= n + 1; j++) {
        if (!vis[j]) {
          dfs(i + 1, j);
          return;
        }
      }
      vis[num] = false;
      dfs(i, num - 1);
    } else {
      for (let j = res[i] - 1; j > 0; j--) {
        if (!vis[j]) {
          dfs(i + 1, j);
          return;
        }
      }
      vis[num] = false;
      dfs(i, num + 1);
    }
  };
  dfs(0, 1);
  for (let i = 1; i <= n + 1; i++) {
    if (!vis[i]) {
      res[n] = i;
      break;
    }
  }

  return res.join('');
}