[HackerRank]愈大愈好(Bigger is Greater)

題目描述

給定一個文字W,請重新排列W的字母使得它構成另一個文字S,且這個文字S的辭典排序必須在文字W之後。由於可能會有很多種答案,請找出並輸出辭典排序在最前面的那個文字。

原題網址

https://www.hackerrank.com/challenges/bigger-is-greater

輸入格式

輸入的第一行為一個整數T,代表測試資料的數量,範圍在1到105之間(包含1和105),接下來的T行每行都是一個文字W,長度在1到100之間(包含1到100),且只由小寫英文字母組成。

輸出格式

重組文字S,找出辭典排序在文字W之後的文字S。這個文字S可能有好幾個,請輸出辭典排序在最前面的那個。如果找不到任何的文字S,輸出「no answer」。

範例輸入

5
ab
bb
hefg
dhck
dkhc

範例輸出

ba
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」即可。

參考答案

關於作者

Magic Len

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章