You are given an array of strings ideas that represents a list of names to be used in the process of naming a company. The process of naming a company is as follows:
Choose 2 distinct names from ideas, call them ideaA and ideaB.
Swap the first letters of ideaA and ideaB with each other.
If both of the new names are not found in the original ideas, then the name ideaA ideaB (the concatenation of ideaA and ideaB, separated by a space) is a valid company name.
Otherwise, it is not a valid name.
Return the number of distinct valid names for the company.
說明
我自己先想了一個解法:
先把資料處理成 map: idea[0] -> set of idea[1:], 然後就可以發現任兩個【第一個字元】所做出的 valid company name 會是$|(set_1 - set_2)(set_2 - set_1)|$,這樣時間複雜度會是 $O(26^2N\lg N)$,空間複雜度是 $O(N\lg N)$。
Tips:
要對 idea[1:] 做離散化,減少 set<idea[1:]> 的操作常數。
計算 set1 - set2 時,可以只迭代較小的 set。
不過後來我看題解是有用另外的解法。我把問題切成 (i, j) 互換,題解再切了一半:只考慮 i → j 的情況,也就是去數多少個 i 可以換到 j 。最後只要把 (|i→j||j→i|) 加起來就好。