AcWing 4607. Java 直接暴力解1914ms
原题链接
中等
import java.util.*;
import java.io.*;
class Main {
static PrintWriter pw;
void solve(char[] s) {
int n = s.length;
boolean ok = false;
for (int i = 0; i + 26 - 1 < n; i++) {
char[] sub = Arrays.copyOfRange(s, i, i + 26);
String[] need = make(sub); // 判断问号是否足够填充没有的字母
if (need[1].equals("good")) { // 找到可填充的情况
String t = need[0];
int p = 0;
for (int j = i, cnt = 0; cnt < 26; j++, cnt++) { // 填充
if (s[j] == '?') {
s[j] = t.charAt(p++);
}
}
ok = true;
break;
}
}
for (int i = 0; i < n; i++) { // 剩余的问号随便填
if (s[i] == '?') s[i] = 'A';
}
pr(ok ? new String(s) : -1);
}
String[] make(char[] a) {
boolean[] has = new boolean[26];
int cnt = 0;
for (char c : a) {
if (c != '?') {
has[c - 'A'] = true;
} else {
cnt++;
}
}
String res = "";
for (int i = 0; i < 26; i++) {
if (!has[i]) res += (char) (i + 'A');
}
String mark = cnt >= res.length() ? "good" : "bad";
return new String[]{res, mark};
}
private void run() throws IOException {
// read_write_file(); // comment this before submission
FastScanner fs = new FastScanner();
char[] s = fs.readLine().toCharArray();
solve(s);
}
private final String INPUT = "input.txt";
private final String OUTPUT = "output.txt";
void read_write_file() {
FileInputStream instream = null;
PrintStream outstream = null;
try {
instream = new FileInputStream(INPUT);
outstream = new PrintStream(new FileOutputStream(OUTPUT));
System.setIn(instream);
System.setOut(outstream);
} catch (Exception e) {
}
}
public static void main(String[] args) throws IOException {
pw = new PrintWriter(System.out);
new Main().run();
pw.close();
}
<T> void pr(T t) {
pw.println(t);
}
class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = nextInt();
return a;
}
String readLine() throws IOException {
return br.readLine();
}
}
void tr(Object... o) {
pw.println(Arrays.deepToString(o));
}
}