字符串查找字符出現次數

Description:

描述：

It's a popular interview question based of dynamic programming which has been already featured in Accolite, Amazon.

這是一個流行的基于動態編程的面試問題，已經在亞馬遜的Accolite中得到了體現。

Problem statement:

問題陳述：

Given two strings S and T, find the number of times the second string occurs in the first string, whether continuous or discontinuous as subsequence.

給定兩個字符串S和T ，找出第二個字符串在第一個字符串中出現的次數，無論是連續的還是不連續的作為子序列。

    Input:
String S: "iloveincludehelp"
String T: "il"
Output:
5

Explanation:

說明：

The first string is,

第一個字符串是

The second string is "il"

第二個字符串是“ il”

First occurrence:

第一次出現：

Second occurrence:

第二次出現：

Third occurrence:

第三次出現：

Fouth occurrence:

發生口：

Fifth occurrence:

第五次出現：

So, total distinct occurrences are 5.

因此，總的不重復發生次數為5。

Solution Approach:

解決方法：

First, we discuss the recursive solution and then we will convert it to dynamic programming.

首先，我們討論遞歸解決方案，然后將其轉換為動態編程。

Prerequisite:

先決條件：

    string s: the first string
string t: the second string
starts: start point of the first string
srartt: start point of the second string
m : length of first string
n : length of second string

How, how can we generate a recursive relation?

如何，如何生成遞歸關系？

Say,

說，

    starts=i where i<m and i>=0 & start=j where j<n and j>=0

Say,

說，

1. s[starts] = t[start] that means both have same character,

   s [starts] = t [start]表示兩個字符相同，

   Now we have to option,

   現在我們必須選擇

   1. Check for starts+1, startt+1 which means we are looking for the same occurrence, we want to check for other characters as well.
   2. 檢查starts + 1 ， startt + 1 ，這意味著我們正在尋找相同的事件，我們也想檢查其他字符。
   3. Check for starts+1, startt which means we are looking for another different occurrence.
   4. 檢查starts + 1和startt ，這意味著我們正在尋找另一個不同的事件。

2. s[starts] != t[start]

   s [開始]！= t [開始]

   Now we have only one option which is check for

   現在我們只有一個選項可以檢查

   starts+1, startt as we need to look for different occurrence only.

   starts + 1 ， startt，因為我們只需要查找不同的事件。

    Function distinctOccurence(string s,string t,int starts,int startt,int m,int n)
if startt==n   //enter substring is matched
return 1;
if starts==m         //enter string has been searched with out match 
return 0;
if(s[starts]!=t[startt])
//only one option as we discussed
return distinctOccurence(s,t,starts+1,startt,m,n); 
else
//both the options as we discussed
return distinctOccurence(s,t,starts+1,startt+1,m,n) + distinctOccurence(s,t,starts+1,startt,m,n);

The above recursion will generate many overlapping subproblems and hence we need to use dynamic programming. (I would recommend to take two short string and try doing by your hand and draw the recursion tree to understand how recursion is working).

上面的遞歸將產生許多重疊的子問題，因此我們需要使用動態編程。 (我建議您取兩個短字符串，然后用手嘗試畫出遞歸樹，以了解遞歸的工作方式)。

Let's convert the recursion to DP.

讓我們將遞歸轉換為DP。

    Step1: initialize DP table
int dp[m+1][n+1];
Step2: convert step1 of recursive function
for i=0 to n
dp[0][i]=0;
Step3: convert step2 of recursive function
for i=0 to m
dp[i][0]=1;
Step4:   Fill the DP table which is similar to step3 of the recursion function
for i=1 to m
for j=1 to n
if s[i-1]==t[j-1]
dp[i][j]=dp[i-1][j]+dp[i-1][j-1]
else
dp[i][j]=dp[i-1][j]
end for
end for
Step5: return dp[m][n] which is the result.

C++ Implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
int distinctOccurence(string s, string t, int starts, int startt, int m, int n) {
//note argument k,l  are of no use here
//initialize dp table
int dp[m + 1][n + 1];
//base cases
for (int i = 0; i <= n; i++)
dp[0][i] = 0;
for (int i = 0; i <= m; i++)
dp[i][0] = 1;
//fill the dp table
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1])
dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1];
else
dp[i][j] = dp[i - 1][j];
}
}
return dp[m][n];
}
int main() {
int n, m;
string s1, s2;
cout << "Enter the main string:\n";
cin >> s1;
cout << "Enter the substring:\n";
cin >> s2;
m = s1.length();
n = s2.length();
cout << s2 << " has " << distinctOccurence(s1, s2, 0, 0, m, n) << " times different occurences in " << s1 << endl;
return 0;
}

Output

輸出量

Enter the main string:
iloveincludehelp
Enter the substring:
il
il has 5 times different occurences in iloveincludehelp

翻譯自: https://www.includehelp.com/icp/find-number-of-times-a-string-occurs-as-a-subsequence.aspx

字符串查找字符出現次數