【833. 字符串中的查找與替換】

來源:力扣(LeetCode)

描述:

你會得到一個字符串 s (索引從 0 開始),你必須對它執行 k 個替換操作。替換操作以三個長度均為 k 的并行數組給出:indices, sources, targets

要完成第 i 個替換操作:

  1. 檢查 子字符串 sources[i] 是否出現在 原字符串 s 的索引 indices[i] 處。
  2. 如果沒有出現, 什么也不做
  3. 如果出現,則用 targets[i] 替換 該子字符串。

例如,如果 s = "abcd"indices[i] = 0 , sources[i] = "ab"targets[i] = "eee" ,那么替換的結果將是 "eeecd"

所有替換操作必須 同時 發生,這意味著替換操作不應該影響彼此的索引。測試用例保證元素間 不會重疊

  • 例如,一個 s = "abc"indices = [0, 1]sources = ["ab","bc"] 的測試用例將不會生成,因為 "ab""bc" 替換重疊。

在對 s 執行所有替換操作后返回 結果字符串

子字符串 是字符串中連續的字符序列。

示例 1:

1

輸入:s = "abcd", indexes = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
輸出:"eeebffff"
解釋:
"a" 從 s 中的索引 0 開始,所以它被替換為 "eee""cd" 從 s 中的索引 2 開始,所以它被替換為 "ffff"

示例 2:
2

輸入:s = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"]
輸出:"eeecd"
解釋:
"ab" 從 s 中的索引 0 開始,所以它被替換為 "eee""ec" 沒有從原始的 S 中的索引 2 開始,所以它沒有被替換。

提示:

  • 1 <= s.length <= 1000
  • k == indices.length == sources.length == targets.length
  • 1 <= k <= 100
  • 0 <= indexes[i] < s.length
  • 1 <= sources[i].length, targets[i].length <= 50
  • s 僅由小寫英文字母組成
  • sources[i] 和 targets[i] 僅由小寫英文字母組成

方法一:按照下標排序 + 模擬

思路與算法

我們直接按照題目的要求進行模擬即可。

首先我們根據數組 indices,將所有的替換操作進行升序排序。在這一步中,同時對 indices,sources,targets 這三個數組進行排序較為困難,我們可以使用一個長度(記為 m)與它們相同的數組 ops,存儲 0 到 m ? 1 這 m 個下標,隨后對 ops 本身按照 indices 作為第一關鍵字進行排序即可。

在排序完成后,我們就可以遍歷給定的字符串 s 進行操作了。我們使用另一個指針 pt 指向 ops 的首個元素,表示當前需要進行的操作。當我們遍歷到第 i 個字符時,我們首先不斷往右移動 pt,直到其移出邊界,或者第 ops[pt] 個操作的下標不小于 iii。此時,會有如下的兩種情況:

  • 如果這個下標大于 i,說明不存在下標為 i 的操作。我們可以直接將第 i 個字符放入答案中;
  • 如果這個下標等于 i,說明存在下標為 i 的操作。我們將 s 從位置 i 開始的長度與 sources[ops[i]] 的子串與 sources[ops[i]] 進行比較:
    • 如果相等,那么替換操作成功,我們將 targets[ops[i]] 放入答案中。由于替換操作不可能重疊,因此我們可以直接跳過 sources[ops[i]] 長度那么多數量的字符;
    • 否則,替換操作失敗,我們可以直接將第 i 個字符放入答案中。

需要注意的是,題目中只保證了成功的替換操作不會重疊,而不保證失敗的替換操作不會重疊。因此當這個下標等于 i 時,可能會有多個替換操作需要進行嘗試,即我們需要不斷往右移動 pt,直到其移出邊界,或者第 ops[pt] 個操作的下標嚴格大于 i。遍歷到的替換操作需要依次進行嘗試,如果其中一個成功,那么剩余的不必嘗試,可以直接退出。

代碼:

class Solution {
public:string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {int n = s.size(), m = indices.size();vector<int> ops(m);iota(ops.begin(), ops.end(), 0);sort(ops.begin(), ops.end(), [&](int i, int j) { return indices[i] < indices[j]; });string ans;int pt = 0;for (int i = 0; i < n;) {while (pt < m && indices[ops[pt]] < i) {++pt;}bool succeed = false;while (pt < m && indices[ops[pt]] == i) {if (s.substr(i, sources[ops[pt]].size()) == sources[ops[pt]]) {succeed = true;break;}++pt;}if (succeed) {ans += targets[ops[pt]];i += sources[ops[pt]].size();}else {ans += s[i];++i;}}return ans;}
};

時間 0ms 擊敗 100.00%使用 C++ 的用戶
內存 9.95mb 擊敗 88.18%使用 C++ 的用戶
復雜度分析

  • 時間復雜度:O(n+mlog?m+ml),其中 n 是字符串 s 的長度,m 是數組 indices 的長度,l 是數組 sources 和 targets 中字符串的平均長度。
    - 排序需要的時間為 O(mlog?m);
    - 在使用雙指針進行遍歷的過程中,遍歷字符串需要的時間為 O(n),遍歷數組 ops 需要的時間為 O(m),在最壞情況下需要嘗試每一個替換操作,比較和構造最終答案需要的時間為 O(ml)。
    相加即可得到總時間復雜度 O(n+mlogm+ml)。
  • 空間復雜度:O(n + ml)。
    - 數組 ops 需要的空間為 O(m);
    - 排序需要的棧空間為 O(log?m);
    - 在替換操作中進行比較時,如果使用的語言支持無拷貝的切片操作,那么需要的空間為 O(1),否則為 O(l);
    - 在構造最終答案時,如果使用的語言支持帶修改的字符串,那么需要的空間為 O(1)(不考慮最終答案占用的空間),否則需要 O(n + ml) 的輔助空間。
    對于不同語言,上述需要的空間會有所變化。這里取每一種可能的最大值,相加即可得到總空間復雜度 O(n + ml)。

方法二:哈希表 + 模擬

思路與算法

我們也可以將方法一中的數組 ops 換成哈希映射,其中的鍵表示字符串中的下標,值是一個數組,存儲了所有操作該下標的操作編號。我們只需要對數組 indices 進行一次遍歷,就可以得到這個哈希表。

在這之后,當我們對字符串 s 進行遍歷時,如果遍歷到位置 i,那么哈希表中鍵 i 對應的數組,就是所有對位置 i 進行的操作。我們使用與方法一相同的方法處理這些操作即可。

代碼:

class Solution {
public:string findReplaceString(string s, vector<int>& indices, vector<string>& sources, vector<string>& targets) {int n = s.size(), m = indices.size();unordered_map<int, vector<int>> ops;for (int i = 0; i < m; ++i) {ops[indices[i]].push_back(i);}string ans;for (int i = 0; i < n;) {bool succeed = false;if (ops.count(i)) {for (int pt: ops[i]) {if (s.substr(i, sources[pt].size()) == sources[pt]) {succeed = true;ans += targets[pt];i += sources[pt].size();break;}}}if (!succeed) {ans += s[i];++i;}}return ans;}
};

時間 0ms 擊敗 100.00%使用 C++ 的用戶
內存 10.12mb 擊敗 59.09%使用 C++ 的用戶
復雜度分析

  • 時間復雜度:O(n+ml),其中 n 是字符串 s 的長度,m 是數組 indices 的長度,l 是數組 sources 和 targets 中字符串的平均長度。
  • 空間復雜度:O(n+ml)。
    author:力扣官方題解

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/37250.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/37250.shtml
英文地址,請注明出處:http://en.pswp.cn/news/37250.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

Spring事務傳播機制

hi ,大家好,繼續為大家帶來Spring事務傳播機制的相關知識 文章目錄 &#x1f917;1.事務傳播機制是什么&#x1f917;2.事務傳播機制作用&#x1f917;3.事務傳播機制 &#x1f917;1.事務傳播機制是什么 定義了多個包含了事務的?法&#xff0c;相互調?時&#xff0c;事務是…

C++教程 - How to C++系列專欄第3篇

關于專欄 這個專欄是優質的C教程專欄&#xff0c;如果你還沒看過第0篇&#xff0c;點擊C教程 - How to C系列專欄第0篇去第0篇 本專欄一致使用操作系統&#xff1a;macOS Ventura&#xff0c;代碼編輯器&#xff1a;CLion&#xff0c;C編譯器&#xff1a;Clang 感謝一路相伴…

[C++ 網絡協議編程] UDP協議

目錄 1. UDP和TCP的區別 2. UDP的工作原理 3. UDP存在數據邊界 4. UDP的I/O函數 4.1 sendto函數 4.2 recvfrom函數 4. 已連接(connected)UDP套接字和未連接(unconnected)UDP套接字 5. UDP的通信流程 5.1 服務器端通信流程 5.2 客戶端通信流程 1. UDP和TCP的區別 主要…

從安全角度分析Angular本地存儲

隨著Web應用程序的不斷增長&#xff0c;前端開發人員慢慢意識到使用瀏覽器提供的本地存儲技術可以在不使用外部數據庫的情況下方便地保存應用程序的數據。Angular作為目前最流行的前端框架之一&#xff0c;也在其API中提供了許多本地存儲技術的支持。但是&#xff0c;在使用本地…

Electron教程_編程入門自學教程_菜鳥教程-免費教程分享

教程簡介 Electron是一個是使用JavaScript&#xff0c;HTML和CSS構建跨平臺的桌面應用程序框架。 Electron 通過將 Chromium 和 Node.js 合并到同一個運行時環境中&#xff0c;并將其打包為 Mac&#xff0c;Windows 和 Linux 系統下的應用來實現這一目的。 Electron入門教程 …

【深度學習】日常筆記16

可以將pd.DataFrame數據結構理解為類似于Excel中的表格。pd.DataFrame是pandas庫提供的一個二維數據結構&#xff0c;用于存儲和操作具有行和列的數據。它類似于Excel中的工作表&#xff0c;其中每一列可以是不同的數據類型&#xff08;例如整數、浮點數、字符串等&#xff09;…

關于安卓打包生成aar,jar實現(一)

關于安卓打包生成aar&#xff0c;jar方式 背景 在開發的過程中&#xff0c;主項目引入三方功能的方式有很多&#xff0c;主要是以下幾個方面&#xff1a; &#xff08;1&#xff09;直接引入源代碼module&#xff08;優點&#xff1a;方便修改源碼&#xff0c;易于維護&#…

Spring_AOP

一、AOP簡介 AOP&#xff0c;Aspect Oriented Programming,面向切面編程,是對面向對象編程0OP的升華。OOP是縱向對一個事物的抽象&#xff0c;一個對象包括靜態的屬性信息&#xff0c;包括動態的方法信息等。而AOP是橫向的對不同事物的抽象,屬性與屬性、方法與方法、對象與對象…

算法訓練營題目day17

110. 平衡二叉樹 給定一個二叉樹&#xff0c;判斷它是否是高度平衡的二叉樹。 本題中&#xff0c;一棵高度平衡二叉樹定義為&#xff1a; 一個二叉樹每個節點 的左右兩個子樹的高度差的絕對值不超過 1 。 func isBalanced(root *TreeNode) bool {h:getHeight(root)if h -1{r…

Vue 安裝開發者工具

1.下載開發者工具&#xff0c;下載地址&#xff1a;http://book.wiyp.top/App/Vue3開發者工具-谷歌/Vue3.crx 2.打開谷歌瀏覽器&#xff0c;點擊擴展&#xff0c;點擊管理擴展程序。 3.開啟開發者模式&#xff0c;將 Vue3 開發者工具文件拖拽到瀏覽器中進行安裝。 注&#xff…

chatGPT小白快速入門培訓課程-001

一、前言 本文是《chatGPT小白快速入門培訓課程》的第001篇文章&#xff0c;全部內容采用chatGPT和chatGPT開源平替軟件生成。完整內容大綱詳見&#xff1a;《chatGPT小白快速入門課程大綱》。 本系列文章&#xff0c;參與&#xff1a; AIGC征文活動 #AIGC技術創作內容征文# …

使用pymupdf實現PDF內容搜索并顯示功能

簡介&#xff1a; 在日常工作和學習中&#xff0c;我們可能需要查找和提取PDF文件中的特定內容。本文將介紹如何使用Python編程語言和wxPython圖形用戶界面庫來實現一個簡單的PDF內容搜索工具。我們將使用PyMuPDF模塊來處理PDF文件&#xff0c;并結合wxPython構建一個用戶友好的…

動態HTTP代理與競爭情報收集的關聯

Hey&#xff0c;各位爬友們&#xff01;作為一名專業的爬蟲HTTP代理提供者&#xff0c;今天我要和大家聊一聊動態HTTP代理與競爭情報收集之間的關聯。在這篇文章中&#xff0c;我將向大家解釋怎么使用動態HTTP代理完成在競爭中的情報收集&#xff0c;并分享一些實用的技巧。 首…

虹科方案 | 汽車總線協議轉換解決方案(二)

上期說到&#xff0c;虹科的PCAN-LIN網關在CAN、LIN總線轉換方面有顯著的作用&#xff0c;尤其是為BMS電池通信的測試提供了優秀的解決方案。假如您感興趣&#xff0c;可以點擊文末相關鏈接進行回顧&#xff01; 而今天&#xff0c;虹科將繼續給大家帶來Router系列在各個領域的…

Netty:判斷ByteBuf底層是否被NIO direct buffer支撐

說明 io.netty.buffer.ByteBuf的函數isDirect()可以判斷該ByteBuf底層是否被NIO direct buffer支撐。如果結果返回true&#xff0c;表示底層被NIO direct buffer支撐。 示例 package com.thb;import io.netty.buffer.ByteBuf; import io.netty.buffer.ByteBufAllocator; imp…

elasticsearch 基礎

ES 搜索技術歷史 今天看的是《Elasticsearch實戰與原理解析》 第一章 搜索技術發展史 1、搜索技術發展史 宏觀而言&#xff0c;搜索引擎的發展經歷了五個尖端和兩大分類。五個階段分別是ftp文件檢索階段、分類目錄階段、文本相關性檢索階段、網頁鏈接分析階段和用戶意圖識別…

算法leetcode|69. x 的平方根(rust重拳出擊)

文章目錄 69. x 的平方根&#xff1a;樣例 1&#xff1a;樣例 2&#xff1a;提示&#xff1a; 分析&#xff1a;題解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 69. x 的平方根&#xff1a; 給你一個非負整數 x &#xff0c…

win10電腦npm run dev報錯解決

npm run dev報錯解決 出現錯誤前的操作步驟錯誤日志解決步驟 出現錯誤前的操作步驟 初始化Vue項目 $ npm create vue3.6.1創建項目文件夾client Vue.js - The Progressive JavaScript Framework? Project name: ? client ? Add TypeScript? ? No ? Add JSX Support? …

【Pytorch:nn.Embedding】簡介以及使用方法:用于生成固定數量的具有指定維度的嵌入向量embedding vector

文章目錄 1、nn.Embedding2、使用場景 1、nn.Embedding 首先我們講解一下關于嵌入向量embedding vector的概念 1&#xff09;在自然語言處理NLP領域&#xff0c;是將單詞、短語或其他文本單位映射到一個固定長度的實數向量空間中。嵌入向量具有較低的維度&#xff0c;通常在幾…

計算機網絡中速率和帶寬的區別

速率&#xff0c;指的是連接在計算機網絡上的主機在數字信道上傳送數據的速率&#xff0c;它也稱為數據率或比特率&#xff0c;單位是bps。速率往往指的是額定速率或者標稱速率&#xff0c;意思也就是在非常理想的情況下才能達到的數據傳送的速率&#xff0c;然而在現實生活中是…