算法:开始字符的题

mood321 · mood321 · commit abe6180db6ee · 2020-08-07T00:50:55.000+08:00
diff --git a/src/main/java/algorithm/Interview/practice05/P_5_1_IsDeformation.java b/src/main/java/algorithm/Interview/practice05/P_5_1_IsDeformation.java
@@ -0,0 +1,38 @@
+package algorithm.Interview.practice05;
+
+/**
+ * @author mood321
+ * @date 2020/8/7 0:34
+ * @email 371428187@qq.com
+ */
+public class P_5_1_IsDeformation {
+
+    /**
+     * 如果字符的类型很多，可以采用哈希表代替长度为256的整型数组，
+     * 字符串的种类为 M，字符串的长度为 N，那么 时间复杂度是 O(N), 空间复杂度是O(M)
+     * @param str1
+     * @param str2
+     * @return
+     */
+    public boolean isDeformation(String str1, String str2){
+
+        if (str1 == null || str2 == null || str1.length() != str2.length()){
+            return false;
+        }
+
+        char[] chars1 = str1.toCharArray();
+        char[] chars2 = str2.toCharArray();
+        int[] map = new int[256];
+
+        for (int i = 0; i < chars1.length; i++) {
+            map[chars1[i]]++;
+        }
+
+        for (int i = 0; i < chars2.length; i++) {
+            if (map[chars2[i]]-- == 0){
+                return false;
+            }
+        }
+        return true;
+    }
+}
diff --git a/src/main/resources/note/Algorithm/程序员面试.md b/src/main/resources/note/Algorithm/程序员面试.md
@@ -713,6 +713,24 @@ N皇后问题是指N*N的棋盘要摆N个皇后，要求任何两个皇后不同
 
 
 
+### 字符串
+
+#### 1 判断两个字符串是否互为变形词
+````
+    　给定两个字符串 str1 和str2 ，如果两个字符串中出现的字符种类一样，次数也一样，则互为变形词，实现一个函数判断两个字符串是否互为变形词。例如 str1=“123”，str2=“132”，true; str1=“123”，str2=“1332”，false;
+    
+    　　
+    
+    　　【解题思路】
+    
+    　　1. 首先比较两个字符串的长度，长度不同肯定是false。
+    
+    　　2. 如果长度相同，新建一个数组，用以存储每个字符出现次数。
+    
+    　　3. 初始值都是为0，在str1 中出现一次就加1，在str2 中出现一次就减1，最后遍历完str2没有出现负值，就返回true。
+````
+<p><a href="/src/main/java/algorithm/Interview/practice04/P_4_17_NQueens.java"> code</a>
+
 
     
 ### 其他
