Commit9555e08

authored

Merge pull requestyoungyangyang04#499 from jackeyjia/patch-18

add js solution for countSubstrings

2 parentsd4e98f4 +08e390c commit9555e08Copy full SHA for 9555e08

File tree

+44

-0

lines changed

+44

-0

lines changed

Lines changed: 44 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -361,7 +361,51 @@ func countSubstrings(s string) int {`
`361`	`361`	`}`
`362`	`362`	```
`363`	`363`
	`364`	`+Javascript`
	`365`	`+> 动态规划`
	`366`	+```javascript
	`367`	`+const countSubstrings = (s) => {`
	`368`	`+const strLen = s.length;`
	`369`	`+let numOfPalindromicStr = 0;`
	`370`	`+let dp = Array.from(Array(strLen), () => Array(strLen).fill(false));`
	`371`	`+`
	`372`	`+for(let j = 0; j < strLen; j++) {`
	`373`	`+ for(let i = 0; i <= j; i++) {`
	`374`	`+ if(s[i] === s[j]) {`
	`375`	`+ if((j - i) < 2) {`
	`376`	`+ dp[i][j] = true;`
	`377`	`+ } else {`
	`378`	`+ dp[i][j] = dp[i+1][j-1];`
	`379`	`+ }`
	`380`	`+ numOfPalindromicStr += dp[i][j] ? 1 : 0;`
	`381`	`+ }`
	`382`	`+ }`
	`383`	`+}`
	`384`	`+`
	`385`	`+return numOfPalindromicStr;`
	`386`	`+}`
	`387`	+```
`364`	`388`
	`389`	`+> 双指针法：`
	`390`	+```javascript
	`391`	`+const countSubstrings = (s) => {`
	`392`	`+const strLen = s.length;`
	`393`	`+let numOfPalindromicStr = 0;`
	`394`	`+`
	`395`	`+for(let i = 0; i < 2 * strLen - 1; i++) {`
	`396`	`+ let left = Math.floor(i/2);`
	`397`	`+ let right = left + i % 2;`
	`398`	`+`
	`399`	`+ while(left >= 0 && right < strLen && s[left] === s[right]){`
	`400`	`+ numOfPalindromicStr++;`
	`401`	`+ left--;`
	`402`	`+ right++;`
	`403`	`+ }`
	`404`	`+}`
	`405`	`+`
	`406`	`+return numOfPalindromicStr;`
	`407`	`+}`
	`408`	+```
`365`	`409`
`366`	`410`
`367`	`411`	`-----------------------`

Comments

(0)