• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

leetcode1625 执行操作后字典序最小的字符串

开发技术 开发技术 6天前 4次浏览

思路:

注意到给定字符串的长度是偶数,所以无论如何操作,所有可能的字符串也只有10 * 10 * n(n是字符串的长度)种,可以暴力枚举。

实现:

 1 class Solution
 2 {
 3 public:
 4     string findLexSmallestString(string s, int a, int b)
 5     {
 6         int n = s.length();
 7         queue<string> q;
 8         q.push(s);
 9         unordered_set<string> st;
10         string res = s; 
11         while (!q.empty())
12         {
13             string tmp = q.front(); q.pop();
14             if (tmp < res) res = tmp;
15             string x = ""; 
16             for (int i = 0; i < n; i++)
17             {
18                 if (i % 2 == 0) x += tmp[i];
19                 else 
20                 {
21                     x += char('0' + (tmp[i] - '0' + a) % 10);
22                 }
23             }
24             if (!st.count(x)) { st.insert(x); q.push(x); }
25             string y = tmp.substr(n - b, b) + tmp.substr(0, n - b); 
26             if (!st.count(y)) { st.insert(y); q.push(y) ;}
27         }
28         return res; 
29     }
30 };

程序员灯塔
转载请注明原文链接:leetcode1625 执行操作后字典序最小的字符串
喜欢 (0)