字串的排序

今日練習的題目是 2273. Find Resultant Array After Removing Anagrams，因為字串長度不大，所以用排序後的字串當作鍵值來比較就可以了。

C++ 字串可以當成陣列直接排序相當方便

class Solution {
public:
    vector< string> removeAnagrams(vector< string>& words) {
        vector< string> ans;
        ans.reserve(words.size());
        string prev;
        for (auto& word : words) {
            string key(word);
            sort(key.begin(), key.end());
            if (key != prev) {
                ans.emplace_back(word);
                prev = move(key);
            }
        }
        return ans;
    }
};

Python3 比較特別有內建的 groupby 可以利用跟搭配 sorted 來產生排序字串當鍵值

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        return [next(g) for _, g in groupby(words, sorted)]

Go 原本是用轉換成排序後的字串當鍵值

func removeAnagrams(words []string) []string {
	var prev string
	ans := make([]string, 0, len(words))
	for _, word := range words {
		runes := []rune(word)
		slices.Sort(runes)
		key := string(runes)
		if key != prev {
			ans = append(ans, word)
			prev = key
		}
	}
	return ans
}

Go 後來發現用 bytes.Equal 直接比較排序後的 []byte 也不錯

func removeAnagrams(words []string) []string {
	prev := []byte{}
	ans := make([]string, 0, len(words))
	for _, word := range words {
		key := []byte(word)
		slices.Sort(key)
		if !bytes.Equal(key, prev) {
			ans = append(ans, word)
			prev = key
		}
	}
	return ans
}

Rust 用轉換排序後的字串當鍵值效率沒那麼好，可能是因為要顧及 UTF-8 的轉換問題

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let mut prev = "".to_string();
        let mut ans = Vec::with_capacity(words.len());
        for word in words {
            let copy = word.clone();
            let mut chars = word.chars().collect::< Vec< char>>();
            chars.sort_unstable();
            let key = chars.into_iter().collect::< String>();
            if key != prev {
                prev = key;
                ans.push(copy);
            }
        }
        ans
    }
}

Rust 改用排序後的 Vec< u8> 陣列直接比較就簡單有效多了

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let mut prev: Vec< u8> = Vec::new();
        let mut ans = Vec::with_capacity(words.len());
        for word in words {
            let mut key: Vec< u8> = word.bytes().collect();
            key.sort_unstable();
            if key != prev {
                prev = key;
                ans.push(word);
            }
        }
        ans
    }
}

Rust 也可以利用 fold 寫出函數式程式設計的風格

impl Solution {
    pub fn remove_anagrams(words: Vec< String>) -> Vec< String> {
        let initial = (Vec::with_capacity(words.len()), Vec::< u8>::new());
        let (ans, _) = words.into_iter().fold(initial, |(mut ans, mut prev), word| {
            let mut key: Vec< u8> = word.bytes().collect();
            key.sort_unstable();
            if key != prev {
                prev = key;
                ans.push(word);
            }
            (ans, prev)
        });
        ans
    }
}