LeetCode 1638. Count the number of substrings with only one character difference

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 and t 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).