LeetCode——デコード方法

Leetcode Decode Ways

A〜Zの文字を含むメッセージは、次のマッピングを使用して数字にエンコードされています。
'A'-> 1
'B'-> 2
..。
'Z'-> 26
数字のみを含む空でない文字列が与えられた場合、それをデコードする方法の総数を決定します。

• 例1：
  入力：「12」
  出力：2
  説明：「AB」（1 2）または「L」（12）としてデコードできます。
• 例2：
  入力：「226」
  出力：3
  説明：「BZ」（2 26）、「VF」（22 6）、または「BBF」（2 2 6）としてデコードできます。

dp [i]で保存される組み合わせの数

public int numDecodings(String s) { if(s.length()==0||(s.length()==1&&s.charAt(0)=='0')) return 0 if(s.length()==1) return 1 int[] dp=new int[s.length()+1] dp[0]=1 for(int i=0i<s.length()i++) { dp[i+1]=s.charAt(i)=='0'?0:dp[i] if(i>0&&(s.charAt(i-1)=='1'||(s.charAt(i-1)=='2'&&s.charAt(i)<='6'))){ dp[i+1]+=dp[i-1] } } return dp[s.length()] }

ランタイム： 1ミリ秒、Decode WaysのJavaオンライン送信の83.92％よりも高速です。
メモリ使用量： 35.9 MB、Decode WaysのJavaオンライン提出の61.71％未満。