X Tutup
Skip to content

Removing Arrays.fill() or for loops, added longest common substring #2027

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
icoder211 wants to merge 10 commits into from
Closed

Removing Arrays.fill() or for loops, added longest common substring #2027

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
d0b43db
Using manual loop to fill DistanceMatrix with 0s
icoder211 Nov 7, 2020
38db103
Removed for loop because initialization by new keyword automatically …
icoder211 Nov 12, 2020
4b55b7a
Fixes #2009
icoder211 Nov 12, 2020
d9e3570
Added Longest common substring, solves #1781
icoder211 Nov 12, 2020
7d9493a
Delete LongestCommonSubstring.java
icoder211 Nov 12, 2020
4c151c6
Added Longest Common substring of two strings
icoder211 Nov 12, 2020
57c6c02
Merge pull request #1 from icoder211/icoder211-patch-1-1
icoder211 Nov 12, 2020
efb418a
Revert "Added Longest Common substring of two strings"
icoder211 Nov 12, 2020
fe48cfa
Merge pull request #2 from icoder211/revert-1-icoder211-patch-1-1
icoder211 Nov 12, 2020
0343228
added longest common substring
icoder211 Nov 12, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion DataStructures/Graphs/FloydWarshall.java
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 +14,7 @@ public FloydWarshall(int numberofvertices) {
[numberofvertices
+ 1]; // stores the value of distance from all the possible path form the source
// vertex to destination vertex
Arrays.fill(DistanceMatrix, 0);
// here the distanceMatrix is initialized by 0s b default upon initialization with new keyword
Copy link
Copy Markdown

@prashantdoshi28 prashantdoshi28 Nov 13, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good, thanks for considering this 👍

this.numberofvertices = numberofvertices;
}

Expand Down
27 changes: 27 additions & 0 deletions DynamicProgramming/LongestCommonSubstring.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,27 @@
public class LongestCommonSubstring {
Copy link
Copy Markdown

@prashantdoshi28 prashantdoshi28 Nov 13, 2020

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you please add problem statement and other relevant info.


public static String string1, string2;
public static int[][] dp;
public static void main(String[] args) {
int res = 0;
string1 = "abbaf";
string2 = "abcdef";
int n = string1.length();
int m = string2.length();
dp = new int[n+1][m+1];
for(int i = 0;i <= n;i++) {
dp[0][i] = 0;
dp[i][0] = 0;
}

for(int i = 1;i <= n;i++) {
for(int j = 1;j <= m;j++) {
if(string1.charAt(i-1) == string2.charAt(j-1)) {
dp[i][j] = 1 + dp[i-1][j-1];
res = Math.max(res, dp[i][j]);
}else dp[i][j] = 0;
}
}
System.out.println(res);
}
}
X Tutup