題目描述
給定一個文字W,請重新排列W的字母使得它構成另一個文字S,且這個文字S的辭典排序必須在文字W之後。由於可能會有很多種答案,請找出並輸出辭典排序在最前面的那個文字。
原題網址
輸入格式
輸入的第一行為一個整數T,代表測試資料的數量,範圍在1到105之間(包含1和105),接下來的T行每行都是一個文字W,長度在1到100之間(包含1到100),且只由小寫英文字母組成。
輸出格式
重組文字S,找出辭典排序在文字W之後的文字S。這個文字S可能有好幾個,請輸出辭典排序在最前面的那個。如果找不到任何的文字S,輸出「no answer」。
範例輸入
ab
bb
hefg
dhck
dkhc
範例輸出
no answer
hegf
dhkc
hcdk
額外解釋
第一組測試資料的文字W為「ab」,重新排列後可以找到符合題目要求的「ba」。
第二組測試資料的文字W為「bb」,不管怎麼排列都是「bb」,所以無法重新排列找到符合題目要求的文字,輸出「no answer」。
第三組測試資料的文字W為「hefg」,重新排列後可以找到符合題目要求的「hegf」。
第四組測試資料的文字W為「dhck」,重新排列後可以找到符合題目要求的「dhkc」。
第五組測試資料的文字W為「dkhc」,重新排列後可以找到符合題目要求的「hcdk」。
解題概念
這題雖然可以把文字W的所有組合都先找出來後再使用辭典排序進行排序,找出我們要的文字S,但這樣效能太差了,必須要使用更有效的方式來進行。
為了要快速找到重新排列後辭典排序會比原本文字W還要後面的組合,我們可以先定位好要重新排列的字元範圍。
舉例來說,「hefg」由於「f」比「g」還排在更前面,所以若將「f」和「g」調換的話可以讓文字的辭典排序更為後面,因次我們也只需要從第三個字元「f」嘗試重新組合即可,因為只需要找到大於原本文字W辭典順序的最小文字(此時i=3)。由於第三個字元「f」的位置只能和最後一個字元調換,所以可以確定我們要的文字就是「hegf」。
再舉一個例子,「dkhc」由於「h」比「c」還排在更後面,僅調換「h」和「c」的話是不會找到符合題目要求的文字的,所以要再更往前看一點。由於「k」比「h」還排在更後面,調換「k」和「h」是沒用的,調換「k」和「c」也是沒用的(因為「h」比「k」還要更前面,「c」一定比「k」還要更前面,調換後無論是「dchk」或是「dckh」都不會比原本的「dkhc」還要來得後面),所以要再更往前看一點。由於「d」比「k」還排在更前面,所以若將「d」和「k」或是「k」之後的字元調換的話,所形成的文字「有可能」會比原本的「dkhc」還要來得後面,並把此時的位置記錄下來,在這個位置之前的字元均不會變動了。為了要再更縮小範圍,把「有可能」化為「一定」,還需從最後一個字元「c」開始到剛才找到的字元「d」,依序尋找字元「d」和是否排在這些字元的前面。由於「d」比「c」還排在更後面,所以要再更往前看一點。由於「d」比「h」還排在更前面,代表把「d」和「h」交換後可以得到比原本「dkhc」還要來得後面的文字,也就是「hkdc」。然而重新排列後,還可以再找到比「hkdc」更前面,卻又比「dkhc」還要更後面的字元組合。由於我們知道原本「d」字元所在位置,也就是目前「h」字元的所在位置,這個位置之前的字元均不必變動,且同樣是這個位置之後的字元是呈現遞減的排序狀態,所以只要將之後的字元進行反轉,變成遞減的辭典排序即可得到題目要求的文字。至於要如何快速將其從遞增反轉成遞減,我們可以將這段範圍的字元視為一個陣列,以中央反射的方式去進行元素的交換,也就是原本第一個元素(最小值)會跟到最後一個元素(最大)交換,而第二個元素(第二小值)則會跟倒數第二個元素(第二大值)交換,依此類推。
若要判斷文字W有沒有解答,在一開始定位的時候,如果無法找到前面的字元比後面的字元之辭典排序還更後面的話,代表原本的文字W已經是辭典排序在最後面的組合了。因此直接輸出「no answer」即可。
參考答案
import java.util.Scanner;
public class Solution {
public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);
final StringBuilder sb = new StringBuilder();
int testCase = Integer.parseInt(sc.nextLine());
while (testCase-- > 0) {
final char[] s = sc.nextLine().toCharArray();
int i = s.length - 1;
while (i > 0 && s[i - 1] >= s[i]) {
--i;
}
if (i == 0) {
sb.append("no answer\n");
continue;
}
int j = s.length - 1;
while (j > i && s[i - 1] >= s[j]) {
--j;
}
swap(s, i - 1, j);
int c = (s.length - i) / 2;
for (int k = 1; k <= c; ++k) {
swap(s, i++, s.length - k);
}
for (i = 0; i < s.length; ++i) {
sb.append(s[i]);
}
sb.append("\n");
}
System.out.print(sb.toString());
}
private static void swap(final char[] s, final int a, final int b) {
final char temp = s[a];
s[a] = s[b];
s[b] = temp;
}
}