当前位置:网站首页>LeetCode 1638. Count the number of substrings with only one character difference
LeetCode 1638. Count the number of substrings with only one character difference
2022-07-06 16:43:00 【Daylight629】
1638. Count the number of substrings with only one character difference
Here are two strings s
and t
, Please find out s
The number of non empty substrings in , These substrings satisfy the substitution A different character in the future , yes t
The substring of a string . In other words , Please find s
and t
In a string just The number of substring pairs with only one character .
For example , "**compute**r"
and "**computa**tion"
The bold part is only one character different : 'e'
/'a'
, So this pair of substrings will add... To the answer 1 .
Please return the number of different substring pairs that meet the above conditions .
One Substring Is a continuous character in a string .
Example 1:
Input :s = "aba", t = "baba"
Output :6
explain : The following is the difference only 1 A character s and t Substring pairs of strings :
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
("aba", "baba")
The bold parts represent s and t String selected substring .
Example 2:
Input :s = "ab", t = "bb"
Output :3
explain : The following is the difference only 1 A character s and t Substring pairs of strings :
("ab", "bb")
("ab", "bb")
("ab", "bb")
The bold parts represent s and t String selected substring .
Example 3:
Input :s = "a", t = "a"
Output :0
Example 4:
Input :s = "abe", t = "bbc"
Output :10
Tips :
1 <= s.length, t.length <= 100
s
andt
All contain only lower case letters .
Two 、 Method 1
violence
class Solution {
public int countSubstrings(String s, String t) {
int res = 0;
int m = s.length();
int n = t.length();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int d = 0;
for (int k = 0; i + k < m && j + k < n; k++) {
if (s.charAt(i + k) != t.charAt(j + k)) {
d++;
}
if (d > 1) {
break;
}
if (d == 1) {
res++;
}
}
}
}
return res;
}
}
Complexity analysis
Time complexity :O(mnmin(m,n)), among m and n They are strings s and t The length of .
Spatial complexity :O(1).
3、 ... and 、 Method 2
Optimize
class Solution {
public int countSubstrings(String s, String t) {
int m = s.length();
int n = t.length();
int res = 0;
for (int d = -m + 1; d < n; d++) {
int i = 0, j = 0;
if (d > 0) {
j = d;
} else {
i = -d;
}
int fij = 0;
int gij = 0;
for (; i < m && j < n; i++, j++) {
if (s.charAt(i) == t.charAt(j)) {
gij++;
} else {
fij = gij + 1;
gij = 0;
}
res += fij;
}
}
return res;
}
}
Complexity analysis
- Time complexity :O((m+n)min(m,n))=O(mn), among m and n They are strings s and t The length of .
- Spatial complexity :O(1).
边栏推荐
- Calculate the time difference
- 第6章 Rebalance详解
- Installation and configuration of MariaDB
- Research Report on market supply and demand and strategy of China's four flat leadless (QFN) packaging industry
- Two weeks' experience of intermediate software designer in the crash soft exam
- 第5章 NameNode和SecondaryNameNode
- OneForAll安装使用
- Chapter 6 rebalance details
- (POJ - 1458) common subsequence (longest common subsequence)
- Tert butyl hydroquinone (TBHQ) Industry Research Report - market status analysis and development prospect forecast
猜你喜欢
Browser print margin, default / borderless, full 1 page A4
Submit several problem records of spark application (sparklauncher with cluster deploy mode)
LeetCode 1552. Magnetic force between two balls
<li>圆点样式 list-style-type
Hbuilder X格式化快捷键设置
Click QT button to switch qlineedit focus (including code)
QT implementation window gradually disappears qpropertyanimation+ progress bar
【锟斤拷】的故事:谈谈汉字编码和常用字符集
Anaconda下安装Jupyter notebook
300th weekly match - leetcode
随机推荐
CMake速成
One hundred questions of image processing (11-20)
【锟斤拷】的故事:谈谈汉字编码和常用字符集
Advancedinstaller installation package custom action open file
Li Kou - 298th weekly match
(lightoj - 1370) Bi shoe and phi shoe (Euler function tabulation)
去掉input聚焦时的边框
第6章 DataNode
Codeforces Round #802(Div. 2)A~D
Spark independent cluster dynamic online and offline worker node
FLV格式详解
字节跳动新程序员成长秘诀:那些闪闪发光的宝藏mentor们
Chapter 2 shell operation of hfds
Chapter 6 rebalance details
Chapter III principles of MapReduce framework
Educational Codeforces Round 122 (Rated for Div. 2)
Educational Codeforces Round 130 (Rated for Div. 2)A~C
拉取分支失败,fatal: ‘origin/xxx‘ is not a commit and a branch ‘xxx‘ cannot be created from it
Chapter 5 namenode and secondarynamenode
Raspberry pie 4B installation opencv3.4.0