Commit84dd3f8

committed

Add C++ implementation

Signed-off-by: begeekmyfriend <begeekmyfriend@gmail.com>

1 parent769617d commit84dd3f8Copy full SHA for 84dd3f8

File tree

+70

-0

lines changed

+70

-0

lines changed

Lines changed: 2 additions & 0 deletions

Lines changed: 43 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,43 @@`
	`1`	`+#include<stdio.h>`
	`2`	`+#include<stdlib.h>`
	`3`	`+`
	`4`	`+`
	`5`	`+staticinlineintmax(inta,intb)`
	`6`	`+{`
	`7`	`+returna>b ?a :b;`
	`8`	`+}`
	`9`	`+`
	`10`	`+intlongestPalindromeSubseq(char*s)`
	`11`	`+{`
	`12`	`+inti,j,k;`
	`13`	`+intlen=strlen(s);`
	`14`	`+int*dp=malloc(lensizeof(int*));`
	`15`	`+for (i=0;i<len;i++) {`
	`16`	`+dp[i]=malloc(len*sizeof(int));`
	`17`	`+memset(dp[i],0,len*sizeof(int));`
	`18`	`+dp[i][i]=1;`
	`19`	`+ }`
	`20`	`+`
	`21`	`+for (k=1;k<len;k++) {`
	`22`	`+for (i=0;i<len-k;i++) {`
	`23`	`+j=i+k;`
	`24`	`+if (s[i]==s[j]) {`
	`25`	`+dp[i][j]=dp[i+1][j-1]+2;`
	`26`	`+ }else {`
	`27`	`+dp[i][j]=max(dp[i][j-1],dp[i+1][j]);`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+ }`
	`31`	`+returndp[0][len-1];`
	`32`	`+}`
	`33`	`+`
	`34`	`+intmain(intargc,char**argv)`
	`35`	`+{`
	`36`	`+if (argc!=2) {`
	`37`	`+fprintf(stderr,"Usage: ./test s\n");`
	`38`	`+exit(-1);`
	`39`	`+ }`
	`40`	`+`
	`41`	`+printf("%d\n",longestPalindromeSubseq(argv[1]));`
	`42`	`+return0;`
	`43`	`+}`

Lines changed: 25 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,25 @@`
	`1`	`+#include<bits/stdc++.h>`
	`2`	`+`
	`3`	`+usingnamespacestd;`
	`4`	`+`
	`5`	`+classSolution {`
	`6`	`+public:`
	`7`	`+intlongestPalindromeSubseq(string s) {`
	`8`	`+int len = s.length();`
	`9`	`+ vector<int>dp(len,1);`
	`10`	`+// We have to use level traverse to reduce the dp table size`
	`11`	`+for (int i = len -2; i >=0; i--) {`
	`12`	`+int left_down =0;`
	`13`	`+for (int j = i +1; j < len; j++) {`
	`14`	`+int down = dp[j];`
	`15`	`+if (s[i] == s[j]) {`
	`16`	`+ dp[j] = left_down +2;`
	`17`	`+ }else {`
	`18`	`+ dp[j] =max(down, dp[j -1]);`
	`19`	`+ }`
	`20`	`+ left_down = down;`
	`21`	`+ }`
	`22`	`+ }`
	`23`	`+return dp[len -1];`
	`24`	`+ }`
	`25`	`+};`

Comments

(0)