從一個字串中刪除另一個字串中的字符
1. 概述
當我們使用 Java 時，我們經常遇到需要精確性和元素之間協作的任務。根據字元在另一個字串中的存在從字串中刪除字元就是這樣的問題。
在本教程中，我們將探索實現此任務的各種技術。
2.問題介紹
像往常一樣，一個例子可以幫助我們快速理解問題。假設我們有兩個字串：
String STRING = "abcdefghij";
String OTHER = "bdfhj";我們的目標是消除STRING字串中的字元（如果它們出現在字串OTHER中） .因此，我們期望得到這個字串作為結果：
"acegi "我們將在本教程中學習解決此問題的各種方法。此外，我們將對這些解決方案進行單元測試，以驗證它們是否產生預期結果。
3. 使用嵌套循環
我們知道使用標準toCharArray()方法可以輕鬆地將字串拆分為char陣列。因此，一種簡單而經典的方法是先將兩個字串轉換為兩個字char陣列。然後，對於STRING中的每個字符，我們透過檢查它是否存在於OTHER中來決定是否要刪除它。
我們可以使用巢狀的 for 迴圈來實作這個邏輯：
String nestedLoopApproach(String theString, String other) {
StringBuilder sb = new StringBuilder();
for (char c : theString.toCharArray()) {
boolean found = false;
for (char o : other.toCharArray()) {
if (c == o) {
found = true;
break;
}
}
if (!found) {
sb.append(c);
}
}
return sb.toString();
}值得注意的是，由於 Java 字串是不可變的對象，因此我們使用StringBuilder而不是「+」運算子來連接字串以獲得更好的效能。
接下來，讓我們建立一個測試：
String result = nestedLoopApproach(STRING, OTHER);
assertEquals("acegi ", result);如果我們執行測試，測試就會通過，因此該方法完成了工作。
由於對於STRING,我們都會檢查字串OTHER ，因此該解決方案的時間複雜度為 O(n 2 ) 。
4. 用indexOf()方法替換內循環
在嵌套循環解決方案中，我們創建了boolean標誌found來儲存當前字元是否已在OTHER字串中找到，然後透過檢查found標誌來決定是否需要保留或丟棄該字元。
Java 提供了String.indexOf()方法，讓我們可以在字串中定位給定的字元。此外，如果字串不包含給定字符，則該方法傳回-1 。
因此，如果我們使用String.indexOf()方法，則不需要內部迴圈和found標誌：
String loopAndIndexOfApproach(String theString, String other) {
StringBuilder sb = new StringBuilder();
for (char c : theString.toCharArray()) {
if (other.indexOf(c) == -1) {
sb.append(c);
}
}
return sb.toString();
}正如我們所看到的，該方法的程式碼比嵌套循環的程式碼更容易理解，並且也通過了測試：
String result = loopAndIndexOfApproach(STRING, OTHER);
assertEquals("acegi ", result);雖然這種實現緊湊且易於閱讀，但由於String.indexOf()方法內部透過循環在字串中搜尋目標字符，其時間複雜度仍然是 O(n 2 ) 。
接下來我們來看看能否找到時間複雜度更低的解法。
5. 使用HashSet
HashSet是一種常用的集合資料結構。它將元素儲存在內部HashMap.
由於雜湊函數的時間複雜度為 O(1)，因此HashSet的contains()方法是 O(1) 運算。
因此，我們可以先將OTHER字串中的所有字元儲存在HashSet中，然後檢查HashSet中STRING中的每個字元：
String hashSetApproach(String theString, String other) {
StringBuilder sb = new StringBuilder();
Set<Character> set = new HashSet<>(other.length());
for (char c : other.toCharArray()) {
set.add(c);
}
for (char i : theString.toCharArray()) {
if (set.contains(i)) {
continue;
}
sb.append(i);
}
return sb.toString();
}正如上面的程式碼所示，實作非常簡單。現在，讓我們深入研究一下它的性能。
最初，我們迭代一個字串來填入Set對象，使其成為一個 O(n) 操作。隨後，對於另一個字串中的每個字符，我們使用set.contains()方法。這導致n倍的 O(1)，成為另一個 O(n) 複雜度。因此，整個解決方案包含兩個 O(n) 操作。
然而，由於因子 2 是常數，因此解的總體時間複雜度仍然是 O(n) 。與先前的 O(n 2 ) 解相比，這是一個顯著的改進，表明執行速度要快得多。
最後，如果我們測試hashSetApproach()方法，它會給出預期的結果：
String result = hashSetApproach(STRING, OTHER);
assertEquals("acegi ", result);六，結論
在本文中，我們探索了三種不同的方法，根據字元在另一個字串中的存在情況從一個字串中刪除字元。
此外，我們也進行了效能分析，明確地關注時間複雜度。結果表明，嵌套循環和使用indexOf()的循環都具有相同的時間複雜度，而使用HashSet解決方案效率最高。
與往常一樣，範例的完整原始程式碼可在 GitHub 上取得。