LeetCode Python/Java/C++/JS > String > 833. Find And Replace in String > Solved in Python > GitHub or Repost
LeetCode link: 833. Find And Replace in String, difficulty: Medium.
You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.
To complete the ith replacement operation:
- Check if the substring
sources[i]occurs at indexindices[i]in the original strings. - If it does not occur, do nothing.
- Otherwise if it does occur, replace that substring with
targets[i].
For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".
All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.
- For example, a testcase with
s = "abc",indices = [0, 1], andsources = ["ab","bc"]will not be generated because the"ab"and"bc"replacements overlap. Return the resulting string after performing all replacement operations ons.
A substring is a contiguous sequence of characters in a string.
Example 1:
Input: s = "abcd", indices = [0,2], sources = ["a","cd"], targets = ["eee","ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".
Example 2:
Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.
Constraints:
1 <= s.length <= 1000k == indices.length == sources.length == targets.length1 <= k <= 1000 <= indexes[i] < s.length1 <= sources[i].length, targets[i].length <= 50sconsists of only lowercase English letters.sources[i]andtargets[i]consist of only lowercase English letters.
Intuition
🚀 While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend Like.dev — the ultimate all-in-one personal branding platform for programmers.
This question looks simple, but it takes a lot of time to do it.
Question 1: For the target string
result, you can clone it based on the original string or build it from an empty string. Which one is better?
Click to view the answer
Cloning based on the original string is better. Because you save a lot of substring assignment operations.
Question 2: After replacing the substring of
resultwithtargets[i], the length ofresultmay change, which makes subsequent replacement difficult. How to solve it?
Click to view the answer
Use technical means to keep the length of
resultunchanged after string replacement.
Complexity
Time complexity
O(N)
Space complexity
O(N)
Explanation
N = s.length
Python #
class Solution:
def findReplaceString(self, s: str, indices: List[int], sources: List[str], targets: List[str]) -> str:
result = list(s)
for i in range(len(indices)):
index = indices[i]
if s[index:index + len(sources[i])] == sources[i]:
for j in range(index, index + len(sources[i])):
if j == index:
result[j] = targets[i]
else:
result[j] = ''
return ''.join(result)
Other languages
Welcome to contribute code to LeetCode.blog GitHub -> 833. Find And Replace in String. Thanks!Level Up Your Developer Identity
🚀 While mastering algorithms is key, showcasing your talent is what gets you hired.
We recommend Like.dev — the ultimate all-in-one personal branding platform for programmers.The All-In-One Career Powerhouse:
- 📄 Resume, Portfolio & Blog: Integrate your skills, GitHub projects, and writing into one stunning site.
- 🌐 Free Custom Domain: Bind your own personal domain for free—forever.
- ✨ Premium Subdomains: Stand out with elite tech handles like
name.cto.pageorname.engineer.dev.- 🔗 Cool Short Links: Get sleek, memorable bio-links like
is.bio/yournameandan.dev/yourname.