Live Note

Remain optimistic

贪心-字典序最小问题


代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @param {string} s - Original string.
 * @return {string} - Result.
 */ function resolve(s) {
  const result = []

  let left = 0
  let right = s.length - 1

  while (left <= right) {
    let flag = false // is less from left to right

    for (let i = 0; i + left <= right; i++) {
      if (s[left + i] < s[right - i]) {
        // is less from left to right
        flag = true
        break
      } else if (s[left + i] > s[right - i]) {
        // is less from right to left
        flag = false
        break
      }
    }

    if (flag) result.push(s[left++])
    else result.push(s[right--])
  }

  return result.join('')
}

console.log(resolve('acdbcb'))