題目
給定一個輸入字符串,字符串只可能由英文字母(a ~ z、A ~ Z)和左右小括號()組成。當字符里存在小括號時,小括號是成對的,可以有一個或多個小括號對,小括號對不會嵌套,小括號對內可以包含1個或多個英文字母也可以不包含英文字母。當小括號對內包含多個英文字母時,這些字母之間是相互等效的關系,而且等效關系可以在不同的小括號對之間傳遞,即當存在a和b等效和存在b和c等效時,a和c 也等效,另外,同一個英文字母的大寫字和小寫字母也相互等效(即使它們分布在不同的括號對里)。
要對這個輸入字符串做簡化,輸出一個新的字符串,輸出字符串里只需保留輸入字符串里的沒有被小括號對包含的字符(按照輸入字符串里的字符順序),并將每個字符替換為在小括號對里包含的字典序最小的等效字符。如果簡化后的字符串為空,請輸出為"0"
示例:輸入字符串為"never(dont)live(run)up(f)()“,初始等效字符集合為(d,o,n,t,r,u,n),由于等效關系可以傳遞,因此最終等效字符集合為(d,n,o,r,t,u),將輸入字符串里的剩余部分按字典序最小的等效字符替換后得到"devedlivedp”
輸入描述
input string
輸入為1行,代表輸入字符串
輸出描述
output string
輸出為1行,代表輸出字符串
備注
輸入字符串的長度在1~100000之間
示例1:
輸入∶
()abd
輸出:
abd
說明:
輸入字符串里沒有被小括號包含的字符串為"abd",其中每個字符沒有等效字符,輸出為"abd"
示例2:
輸入∶
(abd)demand(fb)()for
輸出:
aemanaaor
說明:
等效字符集為(a,b,d, f),輸入字符串里沒有被小括號包含的字符串集合為demandfor”,將其中字符替換為字典序最小的等效字符后輸出為:“aemanaaor”
示例3:
輸入∶
happy(xyz)new(wxy)year(t)
輸出:
happwnewwear
說明:
等效字符集為(w,x,y,z),輸入字符串里沒有被小括號包含的字符串集合為"happynewyear”,將其中字符替換為字典序最小的等效字等后輸出為:“happwnewwear”
思路
比如輸入的字符串為:NeVeD(dont)Live(Drun)up(f)()
按照題意:
先提取小括號(括號內字符數大于1)里的字符:dontDrun,去重后為,dDontru。由于大小寫是等效的,所以這里如果轉為全小寫并去重排序后的結果為:dnortu。于是現在需要將原來字符串中的d,n,o,r,t,u,全部轉為d。得到字符串:deVedLivedp
但是當我們全轉為大寫時,將原來字符串中的d,n,o,r,t,u,全部轉為D,得到結果:DeVeDLiveDp
題目應該是對輸出字符串是忽略大小寫的,否則按照不同方式處理會得到不同的結果。
解題思路如下:
- 首先提取小括號內的字符放入set中去重,小括號內字符個數大于1時才放入set
- 將其他字符(非小括號內的字符)組成新字符串:newStr
- 對set中的字符按照字典序排序,并轉為字符數組:chars
- 對newStr中遍歷,當某個字符出現在chars中時,將它替換為chars[0]
- 最后輸出newStr即可
關鍵在于第1、2步,即將輸入字符串分離為括號內字符和括號外字符兩部分
我們可以使用棧stack來實現,使用sb(StringBuilder)存放括號外的字符,使用set存放括號內的字符,將輸入字符串轉為chars數組,遍歷chars:
- 如果stack為空時,說明沒有出現括號,直接把字符加入sb
- 如果stack不為空或者字符串為(時,說明已經出現了括號,或者第一次出現括號,直接把字符加入stack
- 如果遇到 ),代表一對括號結束,應該清除stack。并且還需要根據括號對中的字符數量判斷是否加入set中。怎么判斷數量?此時stack中的字符為:(、若干字符(stack.size-1),如果字符數量大于1,那么應該將stack中除最后一個(外的字符加入set。
最后考慮特殊情況,比如按照括號對分離后sb為空,直接輸出0,set為空,則直接輸出sb.toString()
題解
package hwod;import java.util.*;public class StringSimplifying {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String str = sc.nextLine();System.out.println(stringSimplifying(str));}private static String stringSimplifying(String str) {Set<Character> set = new HashSet<>();//存儲括號內的字符StringBuilder sb = new StringBuilder();//存儲括號外的字符LinkedList<Character> queue = new LinkedList<>();for (int i = 0; i < str.length(); i++) {if (str.charAt(i) == ')') {if (queue.size() - 1 > 1) {while (queue.size() > 1) {set.add(Character.toLowerCase(queue.pollLast()));//大小寫等效,全轉為小寫}}queue.clear();continue;}if (str.charAt(i) == '(' || !queue.isEmpty()) {queue.addLast(str.charAt(i));continue;}sb.append(str.charAt(i));}if (sb.length() == 0) {return "0";}if (set.size() == 0) {return sb.toString();}ArrayList<Character> chars = new ArrayList<>(set);Collections.sort(chars);final char[] newChars = sb.toString().toCharArray();for (int i = 0; i < newChars.length; i++) {if (chars.contains(Character.toLowerCase(newChars[i]))) {newChars[i] = chars.get(0);}}return String.valueOf(newChars);}
}
推薦
如果你對本系列的其他題目感興趣,可以參考華為OD機試真題及題解(JAVA),查看當前專欄更新的所有題目。